The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field. # 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 . Please do not write to this address regarding general admissions or course queries.