Motivation
A selection algorithm seeks one rank rather than a fully sorted order. Partitioning around a pivot identifies which side contains that rank, so only one side needs further work. If each pivot happens to be the smallest remaining item while the target is largest, the remaining list shrinks by only one and the total work is quadratic. Choosing each pivot uniformly at random changes the analysis: balanced pivots occur often enough to make the expected total work linear for every fixed input.
The result is an expected-cost guarantee over the algorithm's random choices, not a constant worst-case running time. The algorithm always returns the correct rank in the comparison model below; randomness affects the amount of work.
Definitions
Definition 1.11.1
(The selection problem and its cost model)
The input consists of distinct totally ordered items and a valid rank . On a current list of size , choose a pivot uniformly among its items, using fresh random choices conditional on the current list. Partition the remaining items into those smaller and larger than the pivot. If its rank in the current list is , return it. Otherwise continue on the unique side containing the target, adjusting the rank when discarding smaller items and the pivot.
Assume one partition, including pivot selection, costs at most units for a fixed constant , and handling a one-item list costs at most units. We count comparisons or other unit operations in this model. A pivot is balanced in a list of size if its rank lies between and , inclusive.
Theorems
Theorem 1.11.2
(Correctness and termination)
For every sequence of pivot choices, randomized quickselect terminates and returns the requested item.
Theorem 1.11.3
(Expected linear work)
For every fixed input of distinct items and every valid target rank, expected work over the algorithm's random choices is at most a constant times .
Proof sketch or proof idea
Proof
(Correctness and expected linear work)
After partitioning, the pivot's rank is one more than the number of smaller items. If the target equals that rank, the pivot is correct. Otherwise, the target is in the appropriate strict partition, and subtracting the number of discarded smaller items and the pivot gives its rank there. This invariant holds for every pivot choice. A recursive continuation has fewer items than its parent, so the process terminates and the one-item base case is correct.
For a list of size , the number of balanced ranks is
A uniformly selected pivot is therefore balanced with conditional probability at least . On a balanced pivot, both strict partitions have size at most : the smaller side has at most items, and the larger has at most .
Group operations into phases. A phase begins with a current size and ends at the first balanced pivot or when the algorithm terminates. Every operation in that phase handles at most items because sizes only decrease. Conditional on reaching another operation, the chance of a balanced pivot is at least . Hence the probability that a phase continues for at least operations is at most , and its expected number of operations is at most . Its expected work is at most .
After a completed phase, the next phase's starting size is at most three quarters of the preceding phase's starting size. Thus, whether or not all later phases occur, their starting sizes are bounded by . Summing their expected work gives at most
The base case contributes at most a further constant . This proves the expected linear bound. The conditional probability argument remains valid even though the lists reached depend on earlier random choices.
Proof X-ray
Why phases can be summed
Each phase starts no larger than a deterministic geometric bound. Conditional on its entire prior history, each new pivot has at least a one-half chance of ending the phase. Linearity of expectation then sums phase costs without assuming the phase sizes are independent.
Worked examples
Worked example 1.11.4
(A rank update)
Suppose nine distinct items are partitioned into four smaller items, pivot , and four larger items. The pivot has rank five. To find rank seven, recurse on the larger part for rank . The pivot need not be the answer for its partition to be useful.
Worked example 1.11.5
(Balanced ranks)
For a list of size eight, balanced ranks run from through , five possibilities out of eight. If any is chosen, each strict side has at most six items. The general proof only needs the weaker probability bound and the upper bound .
Worked example 1.11.6
(An unlucky sequence)
On a list of size , suppose the target is the maximum and each pivot selected is the current minimum. The partition sizes are , so the work can be quadratic. This pivot sequence has positive probability, even though its probability may be small.
Common mistakes
Counterexample mode
Expected linear does not mean every run is linear
The minimum-pivot sequence above is a valid execution and can take quadratic work. The linear statement averages work over pivot randomness for a fixed input; it is not a per-execution upper bound.
Common mistake
(Demanding the median as the pivot)
A balanced pivot need not be the true median. It only needs to bound both possible retained sides by a constant fraction; ranks through already suffice.
Common mistake
(Treating the pivot ranks across a run as independent)
The phase proof depends on a conditional probability bound at every current list; it does not assume that all pivot ranks across the execution are independent random variables. The lists reached depend on earlier choices, but the bound holds whatever list is reached.
Common mistake
(Forgetting to discard the smaller items from the rank)
If the pivot has smaller items and the target rank satisfies , the new rank is , not . With nine items, pivot rank five and , the target is the second smallest of the four larger items. Seeking rank among those four items is meaningless.
Counterexample mode
A deterministic pivot rule has no expected-linear guarantee
It is tempting to say that the first item of the list is as good a pivot as a random one. Take the sorted list with target rank and always pivot on the first item. The pivot has rank one, so the list is retained with target rank , and so on. The partitions have sizes and make comparisons, on every run, not just an unlucky one. The linear bound needs the uniform conditional pivot distribution, not merely an arbitrary rule.
Following the target rank
The correctness invariant is about the target item, not about the pivot being a good estimate of its rank. Suppose the current target rank is and the pivot has smaller items. If , exactly the same rank is sought among those smaller items. If , the pivot is the answer. If , all discarded items precede the target, so its new rank is in the larger part. Distinctness ensures that every item is in exactly one of the three regions and that the pivot has a unique rank.
The input list is rearranged by partitioning, but no ordering is required within either retained side. Sorting the entire side would add work that this analysis does not charge. The algorithm repeats the rank calculation on the smaller list until the target is found. By contrast, a sorting algorithm normally needs to process both sides; that difference explains why its recurrence can have a different growth rate.
Worked example 1.11.7
(Four possible pivots)
On sorted values , suppose the target is rank two. If the pivot is , the answer is immediate. Pivot retains with target rank one. Pivot retains with target rank two. Pivot retains with target rank two. All four branches are correct; their subsequent costs can differ. Under the balanced definition, ranks one through three are balanced for size four.
Making the phase argument precise
Condition on any history that starts a phase at size . If the algorithm is still running after unbalanced pivots, its current size is at most . For the phase to require a th operation, each of those previous pivots must have been unbalanced and must not have returned the answer. At each step the conditional probability of an unbalanced pivot is at most one half, regardless of the current list and target rank. Multiplying these conditional upper bounds gives probability at most . This is a chain of conditional probabilities; it does not assert that the current list sizes are independent.
For a nonnegative integer-valued random variable , the tail-sum identity follows by writing as the sum of indicators of the events . Applying it to the phase length gives at most two expected partition operations. Each costs at most , so conditioning on the phase's starting history gives expected phase cost at most . The algorithm may finish before a balanced pivot; that can only shorten the phase.
The geometric bound on phase starts is deterministic along every execution. If a phase ends in a balanced pivot and a new phase exists, the next list is no larger than three quarters of the list at that pivot, which is itself no larger than the preceding phase's starting list. Therefore phase starts with at most items. Treat a phase that never occurs as having cost zero. Conditional expectation and the deterministic size bound give the displayed geometric sum even though the number of phases is random.
Expected cost and tail statements
An expectation does not directly say that every run meets a small multiple of . Markov's inequality does give a basic tail bound. If the total work satisfies and , then . For example, at most one tenth of runs have work at least . This bound is valid but can be loose; a stronger tail statement requires a separate proof.
Correctness and running time have different quantifiers here. Every legal pivot sequence returns the correct answer, because each step preserves the rank invariant and strictly decreases the list. The expected-time theorem holds for every fixed input, but averages over the algorithm's random choices. It does not need an assumption that input permutations are equally likely. An adversary who fixes the input before the random pivots are drawn cannot invalidate the conditional uniform-pivot calculation.
The requirement that the current pivot be uniform is substantive. Choosing only the first item from a sorted list is deterministic and can repeatedly choose the smallest item. Choosing a random index once and reusing a deterministic rule after partitioning need not provide a uniform pivot on each subsequent list. The proof asks for the stated conditional distribution at every call; an implementation must justify that its randomization supplies it.
Cost model and boundary cases
Exact uniform sampling of an integer in can be treated as a primitive in a comparison model. If the implementation has only fair random bits, it can draw enough bits to cover a power-of-two range and reject values outside the desired range. That rejection method has a finite expected number of draws, but a detailed bit-cost bound must count the draws and their lengths. The theorem's assumption that pivot selection and partition together cost at most makes this model choice explicit.
The list of size one is a base case. No pivot needs to be selected, and the item is returned. For a valid nonempty list the pivot itself is always discarded or returned, so every recursive continuation is strictly smaller. The proof excludes invalid ranks and an empty input; an implementation should check those preconditions before indexing the list.
With equal keys, a two-way partition must be specified carefully. A common adaptation forms less-than, equal-to and greater-than regions, returning the key when the desired rank falls within the equal region. Its correctness and time analysis require a matching treatment of repeated keys and random pivot selection. The theorem here uses distinct items so that equality with the pivot identifies one item and the simple rank proof applies directly.
Comparing guarantees
Median-of-medians selection supplies a deterministic worst-case linear comparison bound by spending work to choose a pivot with a certified rank range. Randomized quickselect obtains an expected linear bound by sampling a pivot and showing that balanced phases occur quickly on average. The two analyses make different claims about an unlucky individual execution, even though both avoid sorting the entire input.
In practice, pivot choice, memory movement, recursion depth and comparison cost affect performance. The theorem isolates the number of operations under one simple model. It is useful precisely because its assumptions are visible: uniform conditional pivots, distinct keys, linear partition cost and a valid rank. A different implementation should be compared with those assumptions before borrowing the bound.
Summary
Partitioning preserves the target rank and reduces the current list. A uniformly random pivot has a constant chance of discarding a constant fraction, so expected work per phase is linear in that phase's starting size. The starting sizes shrink geometrically after balanced pivots, yielding expected linear total work.
Exercises
Quick check
(If a pivot has four smaller items, what is its rank?)
Solution · Answer
It has rank five.
Quick check
(On a list of size eight, list the balanced ranks under the definition.)
Solution · Answer
They are .
Quick check
(Why can a correct execution still have quadratic work?)
Solution · Answer
An unlucky sequence can retain a list smaller by only one item at each partition, giving a quadratic sum of partition costs.
Quick check
(Is the expected bound an average over a random input distribution?)
Solution · Answer
No. The input is fixed; expectation is over the algorithm's pivot choices.