The words "on average" are not a number

“Quicksort is $\Theta(n \log n)$ on average” is a statement about a distribution. It is delivered as though it were a statement about a number.

The distribution exists, it is not hard to measure, and it contains everything the average discards: the spread, the shape, the tail, and — the part that usually decides whether an algorithm is usable — how bad the bad case is and how often it happens.

What the distribution looks like #

Six hundred independent random inputs at $n = 512$, randomised pivot:

The mean sits 0.8% above the median, which is the signature of a right skew, and the worst run is 32% above the mean. The relative standard deviation is 6.8%.

For a randomised algorithm that is a very well-behaved distribution, and the reason is worth understanding: quicksort’s total cost is a sum of many partition costs, most of which are close to balanced, so the central limit theorem applies and the total concentrates tightly around its mean. A single unlucky pivot near the top of the recursion hurts, but it is one term among many.

The distribution is nonetheless skewed. There is a floor — nothing can average below $\log_2(n!)$, which at $n=512$ is 3,875, and even the luckiest of these six hundred runs came in at 4,282 — and no ceiling short of $n^2/2$. So the distribution has a hard left edge and a long thin right tail, which is the shape almost every cost distribution in this subject has.

Why the tail is the interesting part #

For a batch job that sorts a million arrays and reports total time, the mean is exactly the right statistic: total cost is the sum, and the sum of a million draws is the mean times a million with negligible variance.

For almost anything interactive, it is the wrong statistic, and the reason is arithmetic rather than philosophical.

A web request that performs a hundred independent sorts sees the maximum of a hundred draws from this distribution, not the mean. If each sort’s 99th percentile is 22% above its mean, then a request touching a hundred of them will almost certainly contain at least one sort at that level, and quite possibly several. Tail latency compounds with fan-out, and the more components a request touches, the more the tail of each one governs the whole.

This is why serious systems work quotes p99 and p999 rather than means, and why “average case $\Theta(n \log n)$” is not a specification anyone can build a latency budget from. The distribution is what a budget needs, and the classification never carries one.

The tail does not grow, and that had to be checked #

The measurement above answers a question the classification cannot: does the tail get relatively worse as $n$ grows?

It is easy to imagine that it would. More elements means more pivots means more chances for a bad one. But it also means more terms in the sum, and more terms means tighter concentration. Which effect wins is not obvious from the algorithm and is immediate from the data: the worst-to-mean ratio runs from 1.38 at n = 64 down to 1.18 at n = 2,048, so if anything the tail tightens slightly as n grows. Concentration wins.

That is a real result and it is the kind of thing an average-case bound is silent about. An algorithm whose mean was $\Theta(n \log n)$ and whose 99th percentile grew like $n^{1.5}$ would satisfy every textbook statement about quicksort and be unusable in a latency-sensitive system.

The site’s figure asserts the absence of a trend — if the ratio between the largest and smallest worst-to-mean ratios ever exceeded 2, the figure would fail to build. That is the must-be-able-to-fail discipline applied to a claim about a distribution rather than about a class.

How many samples is enough #

An average computed from a sample is an estimate with an error, and quoting one without knowing the error is the same category of mistake as quoting a class without naming the input.

The question is answerable directly by watching the running mean settle.

The convergence is fast because the distribution is tight. For a heavier-tailed quantity — the number of probes in a nearly-full hash table, say — the same picture would still be wandering after five hundred samples, and the honest response would be to take more or to report a percentile instead of a mean.

Showing the convergence is cheap, and it converts a bare claim of 600 trials into a demonstration that 600 was enough.

The distribution that is not tight #

Randomised quicksort’s distribution is well behaved, and picking it as the example risks suggesting that distributions are usually a formality. They are not, and the contrast is available on this site.

The clean counter-example is a deterministic pivot rule measured across inputs rather than across coin flips. Quicksort taking the first element has a comparison count of 4,887 on random input at $n = 512$ and 130,816 on a sorted one — a factor of 27, and the sorted case is not somewhere in the right tail of the random-input distribution. It is off the chart entirely, three orders of magnitude past the worst random run.

That is what a genuinely heavy-tailed cost looks like, and no amount of sampling from random inputs would ever discover it, because sorted arrays have probability essentially zero under a uniform distribution over permutations. Sampling from the assumed distribution cannot find inputs the assumed distribution does not generate, and real data is not drawn from a uniform distribution over permutations.

This is the practical difference between average-case and expected-case, and it is worth its own essay. A distribution measured over random inputs describes what happens when the data is random. It says nothing about what happens when it is not, and the ways in which real data fails to be random — sortedness, near-sortedness, few distinct values, adversarial construction — are exactly the ways that break these algorithms.

Whose average is it #

There is a question underneath all of this that the word “average” is very good at hiding: averaged over what, and does the reader ever draw from it?

The expected cost of a deterministic algorithm is an average over a population of inputs. A program that sorts a fresh random array every time really does sample that population, and for it the mean is a forecast. A program that sorts the same kind of data every day — a nightly export, a log file, a list that arrives almost in order because it was almost in order yesterday — does not sample it. It draws one point and then draws it again, and if that point is in the tail it is in the tail permanently.

The measurement is easy to arrange. Two hundred runs of first-element quicksort at $n = 512$, each on a different nearly-sorted input generated from a different seed:

The middle row is the one worth sitting with. Its spread is narrower than the random-input row — 1.07 against 1.41 — so by every measure of concentration it is the better behaved distribution. It is also twenty-four times more expensive, every single time, with no bad luck required and no good luck available.

A user whose data looks like that does not experience “quicksort is $\Theta(n \log n)$ on average with a long tail”. They experience a tight, reliable, quadratic cost. The average-case analysis is not wrong; it is an average over a population that includes them at negligible weight, and the answer it reports is an answer about everybody else.

The third row is what randomisation does about it. The same nearly-sorted inputs, a random pivot, and the distribution is back where the analysis says it should be — mean 4,943, spread 1.42, indistinguishable from the random-input row. The randomness has been moved out of the data, where the user controls it and usually does not have any, and into the algorithm, where it is generated fresh on every run. That is the entire trade, and it is worth a separate essay because the guarantee it produces is a different kind of statement rather than a better number.

Three things called “average” #

The word covers three quite different guarantees, and conflating them is the most common error in this area.

Average case. Averaged over an assumed distribution of inputs. Quicksort with a first-element pivot is $\Theta(n \log n)$ in the average case, meaning: given a uniformly random permutation. If the input is sorted — which is an extremely common thing for real data to be — the guarantee does not apply and the algorithm is quadratic. This is the weakest of the three, because it depends on an assumption about the data that may not be checkable and that an adversary can violate deliberately.

Expected. Averaged over the algorithm’s own randomness. Quicksort with a random pivot is expected $\Theta(n \log n)$ on every input, because the randomness is in the coin flips rather than in the data. No input can force the bad case; only bad luck can. This is much stronger, and what randomisation buys is precisely the upgrade from the first guarantee to this one.

Amortised. Averaged over a sequence of operations, with no randomness at all. A dynamic array’s append is $O(1)$ amortised: a worst-case guarantee about the total cost of any sequence. Stronger again, because no distribution is assumed and no luck is involved.

All three get written as “on average” in casual usage. The three underlying guarantees are: if the data is nice, barring bad luck, and always, over the sequence. Those are not close to the same statement.

The shape is the claim, so it is drawn three more times: at four times the size, under a different pivot rule, and on an input that is not random.

The pivot rule is the second dial, and it moves the shape rather than the position — which is the distinction the word average throws away.

And the third dial is the input, which for a randomised pivot ought to do nothing at all. That is worth drawing rather than asserting, because it is the property the randomisation was bought for.

What a distribution figure should show #

Having argued that distributions matter, it is worth being concrete about what to draw, because a histogram is not automatically informative.

The floor, if there is one. Quicksort’s distribution has a hard left edge at $\log_2(n!)$ and knowing that changes how the left tail reads: the mass piled near the bottom is against a wall rather than trailing off.

A high percentile, marked. The 99th is more actionable than the maximum, because the maximum of a sample is itself a highly variable statistic — take another 600 runs and it moves — while the 99th percentile is stable.

The mean, marked, but not alone. Drawing the mean without the spread is what the classification already does.

The sample size and the seeding. A distribution from 600 runs with stated seeds is reproducible; one from Math.random() is a different distribution on every build and its caption cannot be trusted.

Why the shape is always the same #

Almost every cost distribution in this subject has the same shape — a hard floor, a peak near it, and a long thin right tail — and the reason is structural rather than coincidental.

The floor is real. Sorting has an information-theoretic minimum that no input can get under. A hash table insertion takes at least one probe. A dynamic array append costs at least one write. Costs are bounded below by the work that must be done and unbounded above by however badly things can go.

The peak is concentration. Most of these algorithms are sums of many small random contributions — quicksort’s partition costs, a hash table’s probe counts, a random tree’s path lengths — and sums of many independent contributions concentrate. That is the central limit theorem doing what it does.

The tail is the rare compound failure. Getting an unusually bad total requires several of the contributions to be bad at once, which is rare, and the rarity falls off faster than the badness grows. Hence thin.

The practical upshot is that the mean and the median are close for almost everything here, and neither of them is the 99th percentile. Reporting the mean and reporting the median are nearly the same act; reporting either and calling it the cost is the omission.

The arithmetic of fan-out #

The claim that a request touching a hundred sorts “will almost certainly contain at least one at the 99th percentile” is exact enough to compute, and computing it turns a piece of systems folklore into a number that changes what a component should be measured against.

If each sort independently comes in below its own 99th percentile with probability 0.99, then all hundred do with probability $0.99^{100} = 0.366$. Nearly two requests in three contain at least one sort in its top percentile, and the request’s own latency is the maximum rather than the sum of what it fans out to.

Turn that around and ask what a component’s percentile must be for the request to meet a 99th-percentile target. Every component must come in below its threshold with probability $0.99^{1/100} = 0.9999$, so the number to measure and budget against is the component’s p99.99, not its p99. On a hundred-way fan-out the useful statistic is four nines further out than the one anybody reports.

That is why the distribution matters more than any single percentile of it, and it is also why the shape of the distribution decides how bad the news is. Randomised quicksort’s tail is thin: its worst of six hundred runs is 32% above the mean, so even the p99.99 is within a small factor and a fan-out of a hundred costs a modest premium. A heavy-tailed component — one whose p99.99 is ten times its mean — turns the same fan-out into a system whose typical request is dominated by its unluckiest part.

So the tightness of the distribution is not a cosmetic property; it is what decides whether an architecture can fan out at all. The measurement two sections above, that the worst-to-mean ratio does not grow with $n$, is exactly the property a system architect needs and exactly the one the complexity class does not carry.

A fourth thing called average #

Three meanings were separated above and there is a fourth, which is the one a practitioner should usually want and which has no standing in the literature at all.

The measured case. Averaged over the inputs that actually arrive, sampled from production rather than assumed. Not a distribution somebody proved a theorem about, and not a distribution somebody hoped for — the empirical one, taken by recording real inputs and replaying them.

It is the only one of the four that is a statement about a particular deployment, and it is the only one that would have caught the nearly-sorted case in the table above before it became a problem. The average-case bound describes a population the user is not in; the expected-case bound holds but is a bound about coins rather than about the data; the amortised bound is about sequences of operations and says nothing about which inputs they act on. Recording a thousand real inputs and running them settles all three questions at once.

It is also the cheapest of the four to obtain, requiring no theory whatever, which makes its absence from most performance discussions slightly remarkable. The reason is probably that it is not portable — a measured case is a fact about one system’s data and transfers to nobody else — and the literature deals in transferable claims. That is a good reason for a textbook and a poor one for anybody choosing an algorithm for a system whose data they can look at.

The general form of the complaint #

A single number summarising a distribution throws away information, and which information it throws away depends on which number is picked. That is unavoidable and it is not the problem.

The problem is that the convention in this subject is to report one summary — the average — and to report it in a notation that cannot express the others. There is no standard way to write “the 99th percentile is $\Theta(n \log n)$ with constant 1.13”, and so the fact goes unstated, and systems get built on a mean.

Everything on this site that reports an average also reports the distribution it came from, because the distribution is cheap to measure and it is where the surprises are.