Questions / Quant development, Algorithms & structures
Quickselect needs a pivot guarantee
First-element-pivot quickselect looks for the largest of 10 ascending distinct keys. Partitioning m items costs m − 1 comparisons. How many comparisons in total?
Answer it in the app It's free. You get hints, a second try if you miss, and a follow-up question.
Show the answer and worked solution
Answer: 45 comparisons
- Each pivot is the smallest remaining key, so the range shrinks by one.
- The partitions cost 9 + 8 + … + 1.
- That is 45 = 10 × 9/2: quadratic.
Interview shortcut. Σ(m − 1) for m = 10 … 2 = 45.
Takeaway. Bad pivots make quickselect Θ(n²).
In the app this has a follow-up where one thing about the setup changes. Try the follow-up.