Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Average case — where it appears

The mean cost over a stated distribution of inputs, which says nothing without that distribution and is not the same as an expected case. It says nothing without the distribution it averages over, and that distribution is a claim about the world rather than about the algorithm.

Named by 5 essays across 3 fields — each of them below, with the objects they name alongside it.

mean 494599th 60304,2825,4136,543comparisonsruns600 independent random inputs, n = 512worst run 1.32× the mean

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.

wrong · Distribution 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.

wrong · Distribution quicksort on sorted input — comparisonsfirst-element pivot2,096,128random pivot25,318a search tree built from sorted keys — heightbinary search tree2,047treap26a hash table on keys chosen to collide — worst bucketthe low bits of the key2,048multiply–shift, a at random10n = 2,048, bars on a logarithmic scaledeterministic above, randomised below

Expected is not average

Quicksort on 2,048 sorted keys costs 2,096,128 comparisons with a first-element pivot and 25,318 with a random one. A binary search tree on the same keys is 2,047 deep; a treap is 26. A hash table on keys computed against its hash puts all 2,048 in one bucket; one drawn from a family puts at most 10 there. Three problems, one distinction.

bounds · Distribution probe 1: 0–1 absent9 still to ask10 of 10 as good as anyprobe 2: 0–2 absent8 still to ask9 of 9 as good as anyprobe 3: 0–3 absent7 still to ask8 of 8 as good as anyprobe 4: 0–4 present6 still to ask7 of 7 as good as anyprobe 5: 1–2 absent5 still to ask6 of 6 as good as anyprobe 6: 1–3 absent4 still to ask5 of 5 as good as anyprobe 7: 1–4 present3 still to ask4 of 4 as good as anyprobe 8: 2–3 absent2 still to ask3 of 3 as good as anyprobe 9: 2–4 present1 still to ask2 of 2 as good as anyprobe 10: 3–4 absentdecided1 of 1 as good as any5 vertices · 10 pairs · 59,049 states solvedsolid: present · dotted: absent · coloured: this probe

Every pair must be asked

Ask whether a six-vertex graph is connected, one pair of vertices at a time, and the best possible algorithm needs all fifteen questions on its worst graph. The claim that this holds for every monotone property of graphs is a conjecture fifty years old. At four vertices it can be settled completely: all 2,046 properties that do not depend on vertex names need every pair. Name one vertex, and the count drops from ten to four.

floors · Floor length of the longer list, nshorter, m1234561234561floor 12floor 22floor 23floor 33floor 33floor 33floor 34floor 45floor 45floor 56floor 55floor 56floor 67floor 67floor 77floor 78floor 79floor 89floor 810floor 911floor 10the optimum is one above the floorthe floor is reachedevery cell solved exactly · m ≤ n ≤ 6large: the optimum · small: ⌈log₂ C(m+n, m)⌉

The floor a merge cannot reach

Merging two sorted lists of five keys each has 252 possible outcomes, so counting says eight comparisons might do. Solving the game says nine are needed, and on equal lengths the shortfall keeps growing, as half the logarithm of the length. Averaged over random inputs, though, the same count is missed by a tenth of a comparison. The counting floor is nearly exact on average and wrong in the worst case.

floors · Floor

Named alongside it

The objects these essays reach for when they reach for this one.

Comparison countDistributionGuaranteePivotQuicksortWorst caseAdversarial inputAdversary argumentDecision treeExhaustive searchExpected caseHash table

All concepts