$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 lefthand side is$nk − \frac{k(k − 1)}{2} \le n^2 − \frac{k(k − 1)}{2},$
which is indeed smaller than$n^2 + k.$