A distribution computed rather than sampled

Every count on this site is exact, and the ladder that measures counting has spent eight rungs making sure of it: counting instead of timing established the instrument, one run, four counts showed that a single run holds several counts that disagree, and the count that came from somewhere else found a count that belonged to the language’s engine rather than to the algorithm.

That essay ended on an edge of the instrument. A count from a run is a count of one run. For a deterministic algorithm on a stated input that is the whole truth. For a randomised algorithm it is one draw from a distribution — quicksort with a random pivot makes a different number of comparisons each time — and expected is not average made the case that the distribution matters by sampling it: running many times and looking at the spread.

Sampling is an estimate. This page computes the distribution exactly, lays real runs over it, and uses the exact answer to say something sampling cannot say about itself: how many runs a sample needs.

The recurrence, and what it determines #

Quicksort with a pivot chosen uniformly at random from $n$ distinct elements compares the pivot with the other $n - 1$, splits them into the $U$ smaller and the $n - 1 - U$ larger, and recurses on both. $U$ is uniform on $0$ to $n-1$. So the comparison count $C_n$ satisfies

$$C_n = (n - 1) + C_U + C'_{n-1-U},$$

where $C_U$ and $C'_{n-1-U}$ are independent copies for the two sides. That one line determines everything about $C_n$ — not only its mean but its whole distribution — because it expresses $C_n$ in terms of smaller counts whose distributions are, recursively, determined the same way.

The mean follows by taking expectations. Averaging over $U$ gives $E[C_n] = (n-1) + \tfrac{2}{n}\sum_{k<n} E[C_k]$, and solving gives the closed form $2(n+1)H_n - 4n$, where $H_n$ is the harmonic number $1 + \tfrac12 + \cdots + \tfrac1n$. The same answer comes from a different argument: elements of ranks $i$ and $j$ are compared exactly when one of them is the first pivot chosen from the $j - i + 1$ elements between them, which happens with probability $2/(j-i+1)$, and the mean is the sum of those probabilities.

The variance follows the same way, with more algebra, and also has a closed form.

The distribution follows by convolution. The probability that $C_n = c$ is the average, over the $n$ choices of $U$, of the probability that the two sides’ counts add to $c - (n-1)$ — a sum over every way of splitting $c - (n-1)$ between two independent smaller counts. Computing that for every $c$ and every $n$ up to some limit is a table, filled from small $n$ upwards, and the site computes it exactly up to 64 elements.

The site’s check requires the three routes to agree: the convolved distribution’s mean and variance must equal the recurrence’s, and the recurrence’s mean must equal the closed form, to within rounding.

Eight elements #

At eight elements the distribution is small enough to see whole. It runs from a best case of 13 comparisons to a worst of 28, it peaks a little below its mean, and it has a long right tail — the rare runs where a pivot is repeatedly near an end. The mean sits to the right of the peak because the tail pulls it there. The 400 real runs sit on the exact curve within the noise of 400 samples, and their mean is within a hundredth of the exact one.

The picture already says something a mean does not. The worst case, 28, is two thirds again as many comparisons as the mean, and the tail between them is thin but not empty: a run that picks a pivot near an end at the first level and again at the second is not rare at this size. The height is a distribution, and the coin is a parameter made the same observation about skip lists: a randomised structure’s cost is a distribution with a shape, and the shape’s tail is often the part that matters.

Thirty-two and sixty-four #

At 32 elements the distribution has smoothed into a single hump, still skewed right, and the standard deviation has fallen from about a sixth of the mean to about an eighth. That relative narrowing is the whole of the second half of this page, and it is worth noticing where it starts.

The skew does not go away with size. The comparison count of randomised quicksort, centred and scaled by $n$, converges to a limiting distribution that is not normal — a known and somewhat surprising result, since so many sums of random quantities do become normal. A quicksort’s count is a sum, but it is a sum whose terms are not small or independent: the first pivot’s split affects every later comparison. So the right-leaning shape on these plates is not a small-sample effect waiting to disappear; it is the shape of the limit. A limit is not a prediction is the caution that applies in the other direction: the limiting shape describes the count as $n$ grows without bound, and at thirty-two elements the exact distribution on the plate is the object to believe, not the limit it is heading towards.

With a hundred runs the sample has become an unreliable description of the distribution. Its mean is 5.27 comparisons off, which is well within what a hundred samples should give — the standard error is the standard deviation divided by the square root of the run count, $36.7 / 10 = 3.7$, so 5.27 is under one and a half standard errors — but its histogram has gaps and spikes that the exact curve shows are chance. A reader shown only the bars would have no way to tell which features of the histogram belong to quicksort and which to the hundred draws.

With two thousand runs the histogram and the curve agree across the range, and the sampled mean is within four hundredths of the truth. The exact distribution makes it possible to say why that is enough: the standard error is now $36.7/\sqrt{2000} \approx 0.82$, so a mean within about 1.6 of the truth is what 95% of such samples would show, and this sample’s 0.04 is an ordinarily lucky one.

How many runs a sample needs #

The last observation generalises, and it is the point of computing the distribution at all. A sampled mean from $r$ runs has a standard error of $\sigma_n / \sqrt{r}$. For that mean to be within a fraction $p$ of the true mean $\mu_n$ 95% of the time, the standard error must be about $p\,\mu_n / 1.96$, so

$$r = \left(\frac{1.96\,\sigma_n}{p\,\mu_n}\right)^2.$$

Both $\mu_n$ and $\sigma_n$ are exact here, for every $n$, from the recurrence. So the number of runs needed can be computed rather than guessed — and it depends on $n$ through a single ratio, the coefficient of variation $\sigma_n/\mu_n$.

The plate runs against intuition. A larger input is more expensive to run, and a reader might expect it to need more runs to measure well. It needs fewer. Quicksort’s mean grows like $n \log n$ and its standard deviation grows like $n$, so their ratio falls like $1/\log n$, and the runs needed for a fixed relative precision fall like $1/(\log n)^2$. At four thousand elements, eighty-five runs pin the mean to one per cent; at sixteen elements, nearly eight hundred are needed for the same.

Why the spread grows more slowly than the mean #

The shape of that plate comes from two growth rates, and both are known.

The mean is $2(n+1)H_n - 4n$, which grows like $2n\ln n$. The variance, from the same recurrence, grows like $(7 - \tfrac{2\pi^2}{3})\,n^2$, so the standard deviation grows like about $0.65\,n$ — in proportion to $n$, with no logarithm. The coefficient of variation is therefore about $0.65\,n / (2n\ln n) = 0.32/\ln n$, falling as the logarithm grows.

The measured coefficients sit above that approximation — 0.047 at four thousand elements where the formula gives 0.039 — because the lower-order terms of both the mean and the variance are still substantial at these sizes. But the direction and the rate are the formula’s: each quadrupling of the input lowers the coefficient by a roughly constant step, and the runs needed fall by roughly a constant factor.

The intuition behind the $n$ without a logarithm is worth having. Almost all of quicksort’s spread comes from the first few levels of recursion. The first pivot’s rank decides how the whole remaining work divides, and a bad first split changes the total by an amount proportional to $n$. Deeper levels contribute variations proportional to their subarray sizes, which shrink geometrically, so they add a convergent series of smaller terms. The mean, by contrast, gets a contribution proportional to $n$ from every level, and there are about $\log n$ levels — which is where its logarithm comes from and the spread’s absence of one.

What this means for every sampled mean on this site #

Every plate in this collection that reports a mean over randomised runs chose a number of runs, and the choice was a judgement rather than a calculation. The plate above turns the judgement into arithmetic for quicksort, and the arithmetic has a form that transfers: the runs needed are the square of the coefficient of variation, times a constant set by the precision wanted.

That makes two recommendations concrete. Report the standard error beside the mean, since it is the one number that says how much the mean can be trusted and it costs nothing to compute from the runs already made. And scale the runs to the size, since a fixed number of runs gives very different precision at different sizes. Distributions, not averages has argued for reporting the distribution rather than the mean; this rung adds that even the mean, reported alone, owes its reader a precision — and that for an algorithm whose variance is known, the precision can be stated before a single run is made.

That is the number the previous rung said this collection quotes nowhere and relies on everywhere. Every plate that reports a mean over some number of randomised runs is implicitly claiming a precision, and the plate above says what precision a given number of runs buys at a given size. A sweep that uses the same number of runs at every size — the common practice — is measuring its smallest sizes far less precisely than its largest.

The error runs in a direction that matters for fitting a class to the results. The smallest sizes of a sweep anchor the low end of a fitted curve, and a curve fitted through imprecise low points and precise high ones is pulled around by the noise at the end where its constant is decided. A sweep planned with the formula above would run its small sizes longest and its large sizes least, the reverse of the natural temptation — which is to spend runs where each run is cheapest to justify and to stop early where each run is slow.

Extended down to four elements the requirement reaches 1,325 runs, and the line makes the practical recommendation plain: small inputs to a randomised algorithm are the hard ones to measure, and a benchmark that wants equal precision across sizes should run its smallest sizes the most.

A check that could fail, and one that did #

Computing the exact answer also turns a sampled measurement into a test. If the implementation made a different number of comparisons from the recurrence — a partition that compared the pivot with itself, say, or an off-by-one in a loop bound — the sampled mean would sit away from the exact one by many standard errors, and a check can require that it does not.

The site’s check does exactly that at 256 elements with 400 runs: the exact mean is 2,123.91, the standard deviation 159.30, so the standard error is 7.97, and the runs’ mean of 2,121.23 is a third of a standard error away. The check requires agreement within four standard errors. And it is shown to reject: a recurrence that charged the partition $n$ comparisons instead of $n - 1$ — the most common off-by-one in writing one down — predicts a mean of 2,379.9, and the same runs sit 32 standard errors below that. The check must reject asks for exactly this pairing: an assertion that passes on the right model and demonstrably fails on a plausible wrong one.

That is also a better check than comparing against the closed form alone, because the closed form is a single number and a wrong implementation can match a single number by accident. Matching a sampled mean against an exact one, with a tolerance derived from the exact variance, fails every implementation whose count differs by more than a few standard errors, and the exact variance says how small “a few” is.

There is one more resource the random pivot spends that the distribution does not show, and this collection has an instrument for it. Counting the coin flips charged randomised structures for the random bits they consume, and a quicksort with a uniform pivot consumes about $\log_2 k$ bits to choose a pivot from a subarray of $k$ elements, summed over every subarray the recursion visits. That total is itself a random variable with a distribution determined by the same recurrence, and it could be computed exactly the same way. The comparison count and the random bits are two costs of one run, drawn from one sequence of splits, and they are correlated: a run that picks bad pivots early makes more comparisons and visits more subarrays, so it spends more bits too.

What computing the distribution cannot do #

It is only as exact as the recurrence. The recurrence describes a quicksort whose pivot is uniform and whose elements are distinct. Two pivots and what they cost measured a quicksort that is not described by it, and what randomising the pivot buys measured implementations whose pivots are not uniform. For those, the exact distribution on this page is the distribution of a different algorithm, and only sampling measures the real one.

It is expensive to compute beyond small sizes. The moments come from a recurrence with $n$ terms per step and are cheap for any size. The whole distribution comes from a convolution over every split and every count, and its table grows with the square of the largest possible count, which is itself quadratic in $n$; at 128 elements it already takes seconds. So the exact distribution is a tool for small $n$ and for checking, and the exact moments are the tool for planning measurements at any size.

It describes comparisons, not time. Fitting a class to measurements and on average is not a number both warn that a count’s distribution and a running time’s distribution are different objects. The runs needed for a precise mean comparison count are not the runs needed for a precise mean time, which carries the machine’s noise on top.

Where this ladder goes next: a count over every input #

This page removed the randomness from a randomised algorithm’s count by averaging over every random choice exactly. There is a dual: a deterministic algorithm’s count is a function of its input, and averaging, maximising or minimising over every input can also be done exactly — by enumerating the inputs — for small enough sizes.

The next rung does that for five sorts at eight elements, over all 40,320 orderings. It turns out to make a sharp point about benchmarks. A benchmark generator names a handful of inputs — sorted, reversed, nearly sorted, random, few unique — and reports each sort’s count on those. Exhaustive enumeration finds, for three of the five sorts, a worst case that none of the named inputs reaches; for one of them it finds that every named input lands on the sort’s best case. And it confirms one identity this page predicts: the average over every input of quicksort with a fixed first-element pivot is exactly the expected count of quicksort with a random pivot on any input, 16.921 at eight elements, because averaging over inputs and averaging over pivots are the same sum.