Why is an already-sorted input quicksort's worst case with a first-element pivot?
answer
- Ask what each partition step splits off
- How big is the larger side?
- Recursion depth, not just per-level work
- n levels times linear work each
- One element removed per recursive call
basics
~20 sA first-element pivot on sorted data is the smallest element in its range, so each partition splits off one element. The recursion runs n levels deep with linear work per level: O(n^2). Tidy input, maximally unbalanced splits.
solid answer
~40 sQuicksort's cost is (work per level) times (number of levels), and the number of levels is decided by how evenly each partition splits. With the pivot fixed at the first position of an already-ordered range, that pivot is the smallest element, so one side receives zero elements and the other receives n-1. The recursion then has depth n instead of log n while each level still scans its whole range, giving `O(n^2)` time — and `O(n)` recursion depth as space. The same code on a shuffled batch of the same values is `O(n log n)`, which is the point: a case is a statement about the input's relationship to the algorithm's choices, not about the data being tidy. Reverse-sorted input is the mirror image and just as bad.
code
pseudocode · 8 linesquicksort(a, lo, hi):
if lo >= hi:
return
pivot = a[lo]
k = partition(a, lo, hi, pivot) // a[k] holds the pivot afterwards
...
quicksort(a, lo, k - 1)
quicksort(a, k + 1, hi)go deeper
Remember that quicksort's worst case is O(n^2) and that ordinary sorted input triggers it when the pivot is taken from a fixed end. Do not offer O(n log n) as if it were a guaranteed bound.
Explain the mechanism rather than reciting it: an extreme pivot splits off a single element, so recursion depth becomes n and n levels of linear work give n^2. Derive it from the recurrence out loud.
Show that you test with sorted, reverse-sorted and duplicate-heavy inputs, because those are the shapes real pipelines actually deliver and the shapes that turn a routine O(n log n) job into an incident at 3am.
Own the position that a component's worst case, not its typical case, is the risk the organisation carries, and decide deliberately when a bounded-worst-case algorithm is worth a slower average on a critical path.
### Cost follows the split, not the data's tidiness Quicksort works by choosing a pivot, partitioning the current range so that everything on one side is no greater than the pivot and everything on the other is no smaller, and then recursing into the two sides. All the work at one level of recursion is linear in the size of the range being partitioned. So the total cost is (work per level) times (number of levels), and the number of levels is decided entirely by **how evenly each partition splits its range**. Two recurrences bracket the algorithm: - **Even splits:** `T(n) = 2 T(n/2) + O(n)` → depth about log n, total `O(n log n)`. This is quicksort's best case, and also — for a randomly chosen pivot over any input — its expected case. - **Maximally uneven splits:** `T(n) = T(n-1) + O(n)` → depth n, total `n + (n-1) + (n-2) + ... = O(n^2)`. ### Why sorted input hits the second recurrence Fix the pivot at the first position of the range. If the data is already in ascending order, that first element is the **smallest** element of the range. Partitioning therefore puts zero elements on the "less than pivot" side and n-1 on the other. One element is removed from the problem per recursive call, so the recursion has depth n and each level still scans its whole range: `O(n^2)` comparisons, roughly n^2/2 of them. The reverse-sorted case is the mirror image: the first element is now the largest, the split is just as one-sided, and the cost is the same. The lesson is that "sorted" is not a property that makes work easier here — it is a property that makes the *fixed* pivot choice systematically extreme. The same code on a shuffled batch of the same values is O(n log n). The case is a statement about the input's relationship to the algorithm's choices, not about the input being "nice". ### The space cost travels with it Recursion depth is space. The degenerate split gives depth n, so the run that costs O(n^2) time also holds O(n) stack frames. On a large batch that can surface as a stack overflow before the quadratic time is even visible — the failure you actually see is not "slow", it is "crashed", which makes the diagnosis harder than the analysis suggests. ### Why this input, of all inputs, matters in production Adversarial inputs are rare; **already-sorted inputs are everywhere**. Records arrive ordered by ingestion time, exports come out ordered by key, a previous stage sorted the batch and a later stage sorts it again, a test fixture is written in order because that is easier to read. A sort that is fast on shuffled data and quadratic on ordered data will therefore pass every synthetic benchmark and fail on the most ordinary real input there is. If you test one shape beyond random data, test sorted. ### Randomization changes who picks the bad case If the pivot is chosen uniformly at random from the range instead of taken from a fixed end, the worst case does not disappear — no comparison-based partitioning scheme can make an O(n^2) run impossible while the pivot is a single element that might land at an extreme. What changes is its *cause*. The quadratic run now requires nearly every random draw to land near an extreme, whose probability shrinks extremely fast in n; and crucially it is no longer a function of input order, so a sorted batch is just a batch, and a retry is an independent trial rather than a repeat of the same disaster. The expected cost becomes O(n log n) **for every input**, where before it was O(n log n) only for inputs you assumed were shuffled. That is a precise, defensible sentence and it is worth rehearsing: *randomization converts an input-determined worst case into an unlikely, non-repeatable one; it does not convert it into an impossible one.* Claiming "randomized quicksort is O(n log n)" without the word "expected" is the single most common overclaim in this area. ### Numbers worth having straight - Best case and expected case (random pivot): `O(n log n)`; the average number of comparisons over random permutations is about `1.39 n log2 n`, i.e. only ~39% above the ideal. - Worst case: `O(n^2)` time, `O(n)` recursion depth in the naive form. - Big-O is an upper bound, so "O(n^2) worst case" does not say the algorithm behaves quadratically on real data — it says nothing rules that behaviour out. Both halves of that sentence matter when you defend the choice. ### What an interviewer is really checking Not whether you memorized "O(n^2) worst case", but whether you can say **which input** produces it and **why the recursion shape** makes it quadratic — and whether you keep the direction of the claims straight afterwards: unbalanced splits cause depth, depth times linear work causes n^2, and randomization moves the bad case rather than removing it.
- Does choosing the pivot at random make the O(n^2) case impossible?No, it makes it unlikely. A quadratic run now requires nearly every random draw to land near an extreme, whose probability shrinks very fast in n, and it no longer depends on input order. Sorted data becomes just data and a retry is an independent trial, but the worst case still exists — say 'expected O(n log n)', never plain 'O(n log n)'.
- What is quicksort's best case, and how does it arise?A pivot landing near the median at every level, splitting each range roughly in half: depth log n with linear work per level, so O(n log n). That is also the expected case with a random pivot, which is why quicksort's typical behaviour sits close to its best case rather than halfway to its worst.
- Why does the recursion depth matter beyond running time?Because the recursion stack counts as space complexity. The degenerate split gives depth n, so the run that costs O(n^2) time also holds O(n) stack frames. On a large batch that can blow the stack before the quadratic time becomes visible, so the symptom you see is a crash rather than slowness.
It is a tournament in which each round eliminates exactly one player instead of half the field. You need n rounds, not log n.
saying these in an interview costs you the question
- Says sorted input is quicksort's best case
- Claims a random pivot makes O(n^2) impossible
- Quotes O(n log n) as quicksort's worst case
- Ignores that recursion depth becomes n
- Thinks only contrived adversarial inputs trigger it