The Computer Laboratory

Practice Paper 2 Question 11

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.

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Warm-up Questions

  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?

Hints

  • Hint 1
    Find the total time taken for strategy \((1).\)
  • Hint 2
    ... by considering the time taken for each step involved?
  • Hint 3
    In the worst case, what is the least number of comparisons required to find the smallest element of a list?
  • Hint 4
    What is the total time taken to find and remove this element from a list of length \(n?\)
  • Hint 5
    What happens to the length of the list after each removal?
  • Hint 6
    ... and consider that to compute the total time taken for strategy \((2).\)
  • Hint 7
    Try to identify a (useful) upper bound for the time taken for strategy \((2).\)
  • Hint 8
    ... by considering the range of values of \(k\) and the expression for strategy \((1).\)

Solution

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.\)

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.footasc@sulp.ecitcarp. Please do not write to this address regarding general admissions or course queries.