Quickselect runs in expected O(n) — why isn't it the default way to pick the k smallest?

## What the fragment shows The attached pseudocode is quickselect's skeleton. Partitioning is treated as a black box: it splits the current range around one pivot and reports where that pivot finally sits. The interesting part is what happens next — unlike a sort, the routine recurses into **one** side only, because rank `k` can lie in only one of them. ## Where expected O(n) comes from Suppose each partition splits the range roughly in half. The first pass touches `n` elements, the next about `n/2`, then `n/4`, and so on. That geometric series sums to about `2n`, so the total work is linear — no logarithmic factor, because the discarded side is never revisited. That is the whole trick, and it is genuinely a different order of work from a sort. ## Why that is a promise about averages, not about your call Now suppose the pivot lands at the very edge every time: the ranges shrink by one element per pass. The work is `n + (n-1) + (n-2) + ...`, which is O(n^2). With a naive rule like "pivot on the first element," already-sorted input produces exactly that, and input dominated by a handful of repeated key values can behave similarly depending on how the partition handles equal keys. Cheapest catalog prices are, notoriously, both: exports often arrive already ordered, and prices repeat heavily. This is the precise sense in which "expected O(n)" differs from "O(n)". An expected bound averages over the randomness in the algorithm or an assumed input distribution. It is also *not* an amortized bound: amortized bounds cover the total cost of a worst-case **sequence** of operations, and would still guarantee something about the aggregate. Expected guarantees nothing about any individual call — which is exactly what a tail-latency budget cares about. ## The second cost: it eats the input Quickselect achieves O(1) auxiliary space by rearranging the buffer it is given. After the call, the caller's records are in an arbitrary order, and the only structure left is that everything before position `k` is no larger than everything after it. Two consequences: - If some other part of the system depends on the original order — an insertion order, a previously sorted state, a shared cache of records — you must copy the input first, at O(n) time and O(n) space. That copy alone costs as much as the selection. - The result is an unordered prefix. The k cheapest come out as a group, not as a ranking, so a display that wants "cheapest first" needs a further O(k log k) sort of that prefix. A retained-candidate heap sits at the other end of this axis: O(k) extra space, but the input is read-only. ## The third cost: it is offline Quickselect needs random access to the whole range and revisits shrinking sub-ranges repeatedly. That rules out three real situations at once: input that arrives incrementally and must be answered about at any moment; input too large to hold; and input exposed only as a forward, one-shot sequence. A one-pass candidate scan handles all three; a full sort handles none of them in memory either, though external variants exist. ## When quickselect is the right call It is a strong choice — the objection is to it being the *default*, not to the algorithm: - The data is already materialized in a buffer you own and may disturb. - You want the set of k, not a ranking. - `k` is a meaningful fraction of `n`, where the candidate heap's `log k` stops being small and quickselect's linearity actually shows up. - The call is one-shot and offline, so a rare bad case costs a slow batch rather than a violated request SLA. And the mirror image: prefer the scanning heap when input streams or must not be touched; prefer the full sort when ranking is required anyway, or when n is small enough that constants and clarity dominate the asymptotics. ## The misconception to name explicitly "Quickselect is O(n), so it always beats O(n log k) and O(n log n)" fails on three fronts at once: the bound is expected rather than worst-case, the constant factors and memory-access patterns of a partitioning pass are not free, and the algorithm imposes preconditions — full residency, random access, permission to mutate — that the alternatives do not. Comparing algorithms by their headline complexity alone, without their preconditions and side effects, is the single most common way this question is failed.