Why is quickselect only expected O(n), and what input makes it O(n^2)?
answer
- Expected over what, exactly?
- Progress equals how much the range shrinks
- Constant fraction versus constant count
- Sorted input, first-element pivot
- Arithmetic series instead of geometric
basics
~20 sThe linear bound is an expectation over pivot quality, not a guarantee. When pivots keep landing near an end of the range, each round strips off only a few elements, so the shrinking series becomes n + (n-1) + (n-2) + ... and the total reaches O(n^2).
solid answer
~40 sSelection is linear only because each partition is expected to discard a constant fraction of the range. If instead every pivot is the smallest or largest remaining value, the surviving range shrinks by one element per round, and summing `n + (n-1) + (n-2) + ...` gives O(n^2). A deterministic first-element or last-element pivot hits that on already-sorted or reverse-sorted input, which is depressingly common in real data. Randomising the pivot does not make quadratic behaviour impossible; it moves the risk from the *input* to the algorithm's own coin flips, so no adversary can pick a bad input in advance. Say **expected**, not amortized: amortized would bound a worst-case sequence of operations, while this is an average over pivot draws. Median-of-three pivoting improves the common cases but still admits crafted killer sequences.
code
pseudocode · 12 lines// return the value that would sit at index k if a were sorted
lo = 0
hi = length(a) - 1
while lo < hi:
p = partition(a, lo, hi) // pivot ends at its final index p
if k == p:
return a[k]
else if k < p:
hi = p - 1 // whole right side discarded
else:
lo = p + 1 // whole left side discarded
return a[lo]go deeper
Recall that the linear cost assumes pivots split the range decently, and that a pivot which is always the smallest or largest remaining value degrades the routine to quadratic.
Explain the two series side by side: halving gives a geometric sum near 2n, peeling one element gives an arithmetic sum near n^2/2. Then name the input that causes the second.
Demonstrate the vocabulary precisely: expected, average-case and amortized are three different promises. Say what randomisation moves the risk from and to, and when attacker-chosen data turns that into an availability question.
Frame it as a risk decision: which of your paths run on attacker-influenced data, what a rare quadratic pass costs against your latency budget, and whether the guarantee is worth its constant factor across the fleet.
## What the O(n) claim is averaged over The headline result is *expected* linear time, and the expectation is taken over the pivot choices. It is not an average over "typical" inputs, and it is emphatically not an amortized bound. Those three words describe different promises: - **Expected** means averaged over a random variable. With a randomised pivot, the randomness lives inside the algorithm, so the bound holds for *every* input, averaged over the algorithm's own coin flips. - **Average-case** means averaged over an assumed input distribution. If you use a fixed pivot rule, the linear claim degenerates into this weaker form, and it evaporates the moment real data stops matching the assumed distribution. - **Amortized** means the total cost of a worst-case *sequence* of operations divided by their count, with no randomness involved at all. Selection has no amortization story; calling its bound amortized is a vocabulary error interviewers listen for. ## Where the quadratic case comes from Each round costs a linear scan of the surviving range and then keeps one side. Progress is therefore entirely a function of how much the range shrinks: - A pivot near the middle leaves at most about half. Rounds cost `n + n/2 + n/4 + ...`, under `2n`. - A pivot that always splits off a constant fraction, even a lopsided one like 90/10, still leaves a geometric series: `n + 0.9n + 0.81n + ...`, which sums to `10n`. Ugly constant, still linear. - A pivot that is the extreme value of the range leaves `n - 1`. Now the series is arithmetic: `n + (n-1) + (n-2) + ...`, which is `n(n+1)/2`, that is O(n^2). The boundary between linear and quadratic is therefore not "good pivots versus bad pivots" but "constant-fraction shrink versus constant-count shrink". Any pivot rule that guarantees a fixed percentage on the discarded side is linear, however lopsided the percentage. ## Which inputs actually trigger it With a naive rule that always takes the first or last element as pivot, sorted input is the trigger: the first element is the minimum, so partition puts it at index `lo` and the surviving range loses exactly one element every round. Reverse-sorted input does the same. This matters because sorted-ish data is everywhere in practice, arriving from an upstream ordered scan, a previous sort, or a timestamped export, so the pathological case is far more likely than a uniform-random model would suggest. Median-of-three pivoting, which takes the median of the first, middle and last elements, defeats exactly those two patterns and is a genuine improvement. It does not remove the quadratic case: for any *deterministic* pivot rule, an adversary who knows the rule can construct a sequence that feeds it an extreme pivot every round. Such killer sequences have been published for common deterministic rules, and when the input is attacker-controlled that stops being an academic point and becomes an availability concern. ## What randomisation buys, precisely Drawing the pivot uniformly at random from the range changes the quantifier. Instead of "there exists an input that is slow", you get "for every input, the probability of being slow is tiny". The expected number of comparisons is a small constant times n, and the probability of exceeding, say, ten times that decays sharply. Quadratic behaviour is still *possible*: it needs a run of extraordinarily unlucky draws, not a bad input. The distinction matters when reasoning about security. An attacker who can choose the data cannot force the bad case any more, provided the source of randomness is not itself predictable. ## Reading the loop The accompanying fragment is the iterative form. Notice two things. First, there is exactly one recursive direction: the loop either moves `hi` down or `lo` up, never both, which is what keeps the work geometric. Second, the loop's invariant is that the answer's index `k` always lies within `lo..hi`, and it terminates when the range holds one element. If you have said "expected linear", the interviewer's next question is usually "can you make it a guarantee", and the honest answer is that a guaranteed-good pivot exists but costs constants that most callers decline to pay.
- With a randomised pivot, is the expectation taken over inputs or over the algorithm?Over the algorithm's own coin flips. That is the point of randomising: the bound then holds for every input, including one an adversary chose, because the adversary cannot see the draws. A fixed pivot rule only gives you an average over an assumed input distribution, which real data is free to violate.
- Does median-of-three pivoting eliminate the quadratic worst case?No. It kills the everyday triggers, sorted and reverse-sorted input, and improves typical splits. But the rule is deterministic, so a sequence can be constructed that hands it an extreme pivot every round. Only a pivot rule with a guaranteed split fraction removes the quadratic case outright.
- A pivot rule that always splits 90/10 instead of 50/50 costs what?Still linear: n + 0.9n + 0.81n + ... is geometric with ratio 0.9 and sums to about 10n. The constant grows by an order of magnitude, but the asymptotic class does not change. Only a shrink of a constant number of elements per round breaks linearity.
saying these in an interview costs you the question
- Says selection is O(n), full stop
- Calls the linear bound amortized rather than expected
- Claims random pivots make quadratic behaviour impossible
- Thinks already-sorted input is the fast case
- Believes any lopsided split ruins linearity