$k$ smallest elements from a list of length $n.$ Strategy $(1)$ sorts the list in ascending order, which takes time $n^2,$ then removes the first $k$ elements. Strategy $(2)$ repeatedly finds the smallest element by scanning the list and removing it until $k$ elements are removed. The time taken to compare two elements is $1$ and the time taken to remove an element is $1.$ All other operations take zero time. Prove that strategy $(2)$ is faster.
-
- Evaluate the sum
$1+2+\cdots+n.$ - Peter needs to deliver
$n$items to his$n$friends’ houses. He takes$10$minutes to go from his house to any of his friends’ houses, but$k$minutes to go from the$k$th house to the$(k+1)$th house. If he starts from his house, how fast can he deliver all$n$items?
- Evaluate the sum
-
Find the total time taken for strategy
$(1).$ -
… by considering the time taken for each step involved?
-
In the worst case, what is the least number of comparisons required to find the smallest element of a list?
-
What is the total time taken to find and remove this element from a list of length
$n?$ -
What happens to the length of the list after each removal?
-
… and consider that to compute the total time taken for strategy
$(2).$ -
Try to identify a (useful) upper bound for the time taken for strategy
$(2).$ -
… by considering the range of values of
$k$and the expression for strategy$(1).$
-
To execute strategy
$(1),$first sort the list in time$n^2$and then remove the first$k$elements, which takes time$k.$So the total time taken is$n^2 + k.$For strategy
$(2),$to remove the$k$smallest elements, we need to scan through the list, look for the smallest element and remove it, then repeat this process$k$times. For a list of length$i,$finding and removing the smallest element takes time$i$, as we perform$i − 1$comparisons to find it then$1$removal. So the overall time taken for strategy$(2)$is$n+(n − 1)+\cdots+(n − k + 1) = nk − \frac{k(k − 1)}{2}.$To prove that strategy
$(2)$is faster, we must show that$nk − \frac{k(k − 1)}{2} < n^2 + k$for all$n$and all$k.$We know that$1 \leq k \leq n$so an immediate upper bound for the left-hand side is$nk − \frac{k(k − 1)}{2} \le n^2 − \frac{k(k − 1)}{2},$which is indeed smaller than$n^2 + k.$