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
Want the full step-by-step worked solution? It's part of Premium — along with a worked solution for every question in the bank.