Quicksort's worst case, counted
Quicksort partitions around a pivot chosen as the first element of each subarray. You feed it an already-sorted array of distinct numbers - the adversarial input for this pivot rule. Exactly how many element-to-pivot comparisons does it make before finishing?
Show hints (2)+
- On sorted input the first-element pivot is always the minimum, so one side is empty - the worst case.
- Sum ; a partition of elements costs comparisons.
Answer
Reveal answer →Final answer
28
Create a free account to see the full worked solution and track your progress.
Interview format: Hedge Fund Quant, Systematic & Data-Driven Trading