You must remove the $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.
  1. Evaluate the sum $1+2+\cdots+n.$
  2. 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?

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.$