Choose the pivot at random and quicksort's cost stops being a function of the input. Two keys are compared exactly when one of them is the first pivot drawn from the stretch of sorted order between them, which happens with probability 2/(j − i + 1); linearity of expectation adds the indicators up to 2(n+1)Hₙ − 4n. That number is exact, it is under 2n ln n, and it is the same on a sorted array, a reversed one and the array built to destroy median of three.
Core ideas
One hard idea, and it is a shift in what the randomness is about rather than a new technique. The technique is Discrete Mathematics' linearity of expectation.
“Expected Θ(n log n)” here does not mean “Θ(n log n) on a typical array”. Nothing is assumed about the array. The expectation is over the pivot choices the algorithm makes, and it is the same number for every array of n distinct keys — including the one built to destroy median of three. The lab settles this by averaging over every pivot sequence there is, on five different arrays, and getting one fraction.
Write the keys in sorted order as z₁ … zₙ. Two of them are compared only when one is the pivot of a call containing the other, so at most once in the whole run. And they land in different calls as soon as some key strictly between them is chosen as a pivot first. So the event Xᵢⱼ is decided entirely by which element of zᵢ … zⱼ is drawn as a pivot first: zᵢ or zⱼ gives a comparison, any of the others separates them for ever.
There are n(n − 1)/2 indicators and they are not independent: if z₁ and z₉ were compared, that says something about which pivots were drawn, and so about the other indicators. Linearity of expectation does not care. E[ΣXᵢⱼ] = ΣE[Xᵢⱼ] holds for any random variables at all, which is why this derivation is three lines rather than a case analysis.
The material
Why two keys are compared with probability two over their distance, and how the double sum collapses to a harmonic number.
Randomised quicksort is quicksort with one change: the pivot of each call is chosen uniformly at random from that call's range. The input is not shuffled and nothing is assumed about it. Every run on the same array may cost a different number of comparisons.
Rename the keys by rank: z₁ is the smallest, zₙ the largest. This is a relabelling, not an assumption — the algorithm never sees the names. Let Xᵢⱼ be 1 if zᵢ and zⱼ are compared at some point during the run and 0 otherwise, and let X be the total number of comparisons, which is the sum of the Xᵢⱼ over all i < j.
For i < j, the keys zᵢ and zⱼ are compared during the run if and only if the first pivot chosen from among zᵢ, zᵢ₊₁, …, zⱼ is zᵢ or zⱼ. Consequently P(Xᵢⱼ = 1) = 2/(j − i + 1).
All of zᵢ … zⱼ begin in the same call, since every call holds a contiguous stretch of sorted order and this stretch has not been split yet. Consider the first pivot drawn from that stretch.
If it is some z_m with i < m < j, then zᵢ goes to the left side and zⱼ to the right, they are never in the same call again, and they are never compared: a comparison only ever happens between a pivot and another element of the same call. If it is zᵢ or zⱼ, that one is the pivot of a call containing the other, so the two are compared exactly then.
Every element of the stretch is equally likely to be the first of the stretch drawn, because each call draws uniformly from its range. The stretch has j − i + 1 elements and two of them give a comparison, so the probability is 2/(j − i + 1).
□
The inner sum is a tail of the harmonic series, and collecting the identical terms across the outer sum gives the closed form. The bound Hₙ < 1 + ln n turns it into 2n ln n, which is the form usually quoted — but the closed form is exact and the lab prints it as a fraction, because Hₙ is computed as a rational and not as a float.
At n = 9 the closed form is 2593/126 = 20.5794 comparisons, with H₉ = 7129/2520. The lab computes the same number twice more. Once by solving T(n) = (n−1) + (1/n)Σ(T(i) + T(n−1−i)) from the bottom, which contains no harmonic number at all. And once by enumerating every one of the 4 862 possible pivot sequences on the array on screen and averaging exactly. Three definitions, one fraction.
That third row is the one that matters, because it is not a sample. It is a claim about every run of the algorithm on that array, computed rather than argued. Run it on a sorted array, a reversed array, an up-then-down array, a seeded shuffle and the median-of-three killer, and all five give 2593/126. The expectation does not know which array it was handed, which is exactly what the derivation said.
Beside those exact rows the lab prints a mean over seeds, and that one is a sample. 120 seeds on the killer array at nine keys average 20.6583, which is 0.0790 above the expectation. Move the first seed and the row moves; nothing above it does. The gap is sampling, and the honest description of it is “120 of the 4 862 runs”.
The derivation used distinct keys twice: once in the relabelling and once in the claim that a comparison between a pivot and an element sends the element to one side or the other. On an array of 24 equal keys, Lomuto sends every key to the same side, the split is 0 and n − 1 under every seed, and the cost is 276 comparisons while 2(n+1)Hₙ − 4n at 24 is 92.7979. The formula has not been beaten; it was never a claim about that array. Sorting with many equal keys wants a three-way partition, which this course does not cover.
This is the pattern the rest of the path follows. An expectation over the algorithm's own coins holds for every input; an expectation over a distribution of inputs holds only while the distribution does. “Bucket Sort and Average-Case Claims” is the second kind, put beside this one on purpose.
Interactive
The exact fraction, the recurrence that produces it, and a mean that only approaches it
Method
The order below is the order the argument is usually got wrong in: naming the indicator last, and the event never.
Decide exactly what Xᵢⱼ is 1 for. Here: the i-th and j-th smallest keys are compared at some point in the run. Not “compared at this level”, not “in the same call”. The event has to be something you can compute a probability for.
Ask what single random choice settles whether the indicator is 1. Here it is which element of zᵢ … zⱼ is drawn as a pivot first, and once that is seen the probability is a count: two favourable out of j − i + 1.
E[ΣXᵢⱼ] = ΣE[Xᵢⱼ] needs nothing from the indicators. Re-index the double sum by the distance d = j − i so that identical terms collect, and the harmonic number appears.
Compute the closed form as a fraction, take a mean over seeds, and print the difference. If the difference shrinks as the seed count grows, that is sampling; if it does not, one of the two is wrong.
This is the test of the whole claim. Switch the input from sorted to the median-of-three killer: the exact rows do not move and the measured mean does. If the exact rows moved, the derivation would have used a property of the input.
Set the length to 9, the array to the median-of-three killer, the seeds to 120 and the first seed to 1. The array on screen is 1 9 4 8 2 3 5 7 6, which is a permutation of 1 … 9 built to be bad for a deterministic rule and which is about to make no difference at all.
The first five rows are exact and the sixth is not, and the difference between those two situations is the lesson. Rows three to five are not samples either: each is an average over all 4 862 executions, weighted by probability, so each is a complete statement about every run of the algorithm on that array.
The last row is 0.0790 above the expectation. That is what a sample of 120 out of 4 862 looks like. Drag the seed count to 300 and it lands at 20.5300, now below — a running mean wandering toward a level line, which is what the plot draws.
For a faded rehearsal, do the same derivation at n = 8. The supplied first move is H₈ = 761/280; work out 2 · 9 · 761/280 − 32 as a fraction, check it against the panel's first row at n = 8, and then say — before looking — what the enumeration row will show, and how many executions it will report.
You should be able to state the comparison criterion and prove it, get 2/(j − i + 1) by counting, collapse the double sum to 2(n+1)Hₙ − 4n, evaluate it as a fraction at a given n, and explain why a mean over seeds differs from it.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.