Algorithms & Data Structures
the bound is a claim, and it is checkable
What is taught wrongly

The words "on average" are not a number

Quicksort is Θ(n log n) on average. Six hundred runs at n = 512 give a distribution with a mean of 4,945 comparisons, a median of 4,908, and a worst case 32% above the mean. The average is a summary of that picture, it is the least interesting thing in it, and it is almost always the only thing reported.
14 min read 6 figures Distributions, not averagesMeasured, not asserted

“Quicksort is Θ(nlog⁡n)\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.

600 runs of quicksort, random pivot at n = 512Every bar is the number of independent random inputs that cost that many comparisons. The mean is 4945; the median is 4908; the worst of 600 runs cost 6,543, which is 1.32 times the mean. The distribution is tight — a relative standard deviation of 6.8% — and skewed to the right, which is the shape that makes "on average" a defensible thing to say about this algorithm and a misleading thing to say about the version that takes the first element as its pivot.mean 494599th 60304,2825,4136,543comparisonsruns600 independent random inputs, n = 512worst run 1.32× the mean
Fig. 1 Six hundred runs of randomised quicksort at n = 512, one bar per bucket of comparison counts. The mean is a single vertical line through this. The distribution is tight — a relative standard deviation of 6.8% — and visibly skewed to the right, which is the shape that makes “on average” a defensible thing to say about this algorithm.

What the distribution looks like

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

statistic comparisons
best of 600 4,282
median 4,908
mean 4,945
99th percentile 6,030
worst of 600 6,543

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!)\log_2(n!), which at n=512n=512 is 3,875, and even the luckiest of these six hundred runs came in at 4,282 — and no ceiling short of n2/2n^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 Θ(nlog⁡n)\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 whole range, not the mean — quicksort, random pivotAt each size, the vertical bar spans the best and worst of 200 random inputs, with the mean marked and the information-theoretic floor drawn beneath. The worst run is between 1.18 and 1.38 times the mean and that ratio does not grow with n, so the tail is keeping pace with the average rather than outrunning it. The mean sits about 1.29× the floor throughout.641282565121024204810³10⁴ncomparisonsworst runmeanfloor200 random inputs at each sizerange, not average
Fig. 2 The whole range at each size rather than the mean: the bar spans the best and worst of two hundred random inputs, with the mean marked and the information-theoretic floor beneath. The worst-to-mean ratio does not grow with n — the tail keeps pace with the average rather than outrunning it — which is a genuinely reassuring property and one that has to be measured to be known.

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 nn 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 Θ(nlog⁡n)\Theta(n \log n) and whose 99th percentile grew like n1.5n^{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 average, as it settles — 500 runs at n = 256The running mean of the comparison count over independent random inputs. After twenty runs it is already within 1.8% of its final value of 2119, and after a hundred it is visually settled. This is why the average-case figures elsewhere on the site are quoted from a few hundred trials rather than from thousands: the estimate stops moving long before the sample gets expensive.202621182211settles at 21191100250500runs included in the averagemean comparisonsn = 256, independent random inputsan average is an estimate with an error
Fig. 3 The running mean of the comparison count over five hundred independent inputs at n = 256. After twenty runs it is within a fraction of a percent of its final value; after a hundred it has visually stopped moving. This is why average-case figures elsewhere on the site quote a few hundred trials — the estimate settles long before the sample gets expensive, and the settling is shown rather than assumed.

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=512n = 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.

Quicksort, first-element pivot on four kinds of inputThe same algorithm, the same range of n, four input distributions. The best and worst differ by a factor of 83 at n = 2048, so a single complexity class describes this algorithm only if the input is also stated.10010³10³10⁴10⁵10⁶ncomparisonsrandomnearly sortedalready sortedreversedthe textbook trap: quadratic on exactly the input people test withcomparisons, counted exactly
Fig. 4 The heavy tail that sampling cannot find. Quicksort with a first-element pivot on four inputs: the random line is one class and three of the others are another. A distribution measured over the first line would give no hint that the other three exist.

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 Θ(nlog⁡n)\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 Θ(nlog⁡n)\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)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.

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!)\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.

What randomising the pivot buys, n = 512For each pivot rule: the range of comparison counts over 400 random inputs (the bar), and the count on an already sorted array (the marker). Taking the first element as pivot costs 130,816 comparisons on sorted input — 26 times its random-input mean, and the quadratic behaviour the algorithm is supposed to avoid. Choosing the pivot at random costs 5,490 on the same input. Randomisation does not make the bad case impossible; it makes it independent of the input, so an adversary who knows the data cannot choose it.first-element pivot130,816 on sortedmedian of three5088 meanrandom pivot4937 meanblue bar: range over 400 random inputs · marker: the already-sorted inputn = 512a bad case that cannot be chosen is a different kind of bad case
Fig. 5 What the same measurement looks like when a distribution is compared against a single catastrophic point. The blue bars are the range over four hundred random inputs for each pivot rule; the markers are the cost on an already sorted array. For the first-element rule the marker is far outside its own distribution — the sorted case is not in the tail, it is off the chart — and no summary of the random-input distribution would have predicted it.

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.

600 runs of quicksort, first-element pivot at n = 512Every bar is the number of independent random inputs that cost that many comparisons. The mean is 4944; the median is 4889; the worst of 600 runs cost 6,137, which is 1.24 times the mean. The distribution is tight — a relative standard deviation of 6.4% — and skewed to the right, which is the shape that makes "on average" a defensible thing to say about this algorithm and a misleading thing to say about the version that takes the first element as its pivot.mean 494499th 58804,3005,2196,137comparisonsruns600 independent random inputs, n = 512worst run 1.24× the mean
Fig. 6 The same distribution shape for a different pivot rule, over random inputs. Hard left edge, peak, thin right tail — the shape is not a property of randomised quicksort in particular. What differs between rules is where the distribution sits and, crucially, what happens on inputs this picture never samples.

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 Θ(nlog⁡n)\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.

Where this goes next

first-element pivot130,816 on sortedmedian of three5088 meanrandom pivot4937 meanblue bar: range over 400 random inputs · marker: the already-sorted inputn = 512a bad case that cannot be chosen is a different kind of bad case What randomising the pivot buys Quicksort taking the first element as its pivot costs 130,816 comparisons on an already sorted array of 512 — 27 times its cost on random data, and exactly the quadratic behaviour the algorithm exists to avoid. Randomising the pivot costs 5,490 on the same input. Randomisation does not make the bad case impossible; it makes it unchoosable. 110100257amortised 2.000256512append numbercost of that append (log scale)growth factor 2, cost = 1 write + a copy of the array when it resizes9 resizes in 512 appends What amortised means Appending to a dynamic array is O(1) amortised. It is also, on 512 appends, an operation that costs one unit 503 times and 257 units once. The amortised bound is a true statement about the sequence and a false one about any append in it, and the picture that shows why is a sawtooth nobody draws. 10010³10010³10⁴10⁵10⁶ncomparisonsInsertionHeapsortMergeShellsorta power law is a straight line herecomparisons, counted exactly What O-notation does not say Big-O is a statement about a limit. It does not say how fast, it does not say which is better, it does not say anything at all about any particular n, and it discards precisely the factor that usually decides the answer. Knowing exactly what it claims is the difference between using it and being misled by it.