The thread: Distributions, not averages
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.
StructuresWhat 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.
When the algorithm flips a coinThe height is a distribution, and the coin is a parameter
A skip list over 2,048 keys is described as being about log₂ n levels tall. Across two hundred builds of exactly those keys its height ranged from 9 to 19. The number in the description is the mean of something, and choosing the coin is choosing which something.
What is taught wronglyWhat 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.
What a bound isWhat derandomising costs
Randomised selection finds the median of twenty thousand elements in 3.21 comparisons per element and median-of-medians takes 8.15 — two and a half times as many for the same answer, both linear. The number that decides between them is not either of those. It is that the first varies by 28% from seed to seed and the second by 1.6%.
When the algorithm flips a coinThe second choice
Two hundred and sixty thousand keys into as many buckets. Under one hash the busiest bucket holds eight; under two, with each key going to whichever of its two is emptier, it holds four. The mean is exactly one in both. Nothing is rearranged afterwards, no key is ever moved, and the whole of the improvement is in a decision taken once, at the moment the key arrives.
When the algorithm flips a coinAn insertion that can fail
Every randomised structure in this field buys an expected cost and accepts a tail. Cuckoo hashing buys a worst case — a lookup examines exactly two slots, for any keys, always — and pays for it in the construction, which can fail outright. On a table of four thousand slots the construction never fails below 0.45 keys per slot and fails nineteen times in twenty above 0.55.
One pass, and no roomThe estimate that squares the stream
The length of a stream is a counter and the number of distinct keys is a register bank. The sum of the squared frequencies has nothing obvious to count — and one number, one sign per key, and a squaring get within 4% of it in a fortieth of the space.
StructuresThe probe nobody waits for
Robin Hood hashing makes an inserting key steal a slot from a key that has probed less far. The mean number of probes afterwards is 4.817, and before it was 4.817 — identical, and it cannot be otherwise, because the total displacement is fixed by the hash. What changes is the worst case, from 114 slots from home to 19, and a table reported by its average lookup cost shows no difference at all.
What is taught wronglyThe window that is not full
A structure sized for a window of 256 items meets a stream that hands it 1,736 at the worst instant and 79 at the best. Occupancy was a constant in the model the sizing came from, and every per-item bound in that model quietly assumed it.
StructuresA bucket that becomes a tree
Java's HashMap converts a chained bucket into a red-black tree once it holds eight entries. The comment in the source computes the probability of that happening under a decent hash at about six in a hundred million, so the mechanism is written never to run. Under a hash that fails, the worst lookup falls from 192 comparisons to 8 — and the whole value of the tree is in a case its author does not control.
When the algorithm flips a coinThe estimate that is a median of means
An estimator with a 70% spread is not usable and an estimator with a stated failure probability is. The construction that turns the first into the second is two lines long, it is where every delta in this field comes from, and its exponential is measured here by counting failures rather than by evaluating a bound.
CountingA distribution computed rather than sampled
Quicksort with a random pivot makes a random number of comparisons, and every plate in these essays reports one draw from that distribution. The distribution itself can be computed exactly — every pivot, every split, weighed — and on sixty-four elements its mean is 360.706 and its standard deviation 36.741. A hundred real runs average 365.98; two thousand average 360.74. The exact answer says how many runs a sample needs, and it is fewer as the input grows.
What the libraries doSized for a rate that does not hold still
A four-second window on a stream at a hundred arrivals a second holds four hundred items on average and between 105 and 2,169 when the rate moves. An allocation set at that average overflows at 47 per cent of instants while 35 per cent of it stands empty, which is the same decision failing in both directions at once.
One pass, and no roomAn error measured against the answer
A quantile summary asked for the 99.9th percentile answered 9,694 where the truth was 256, and violated nothing — its promise was a rank error under one per cent of the stream and it delivered a tenth of one per cent. One per cent of the stream is a thousand per cent of the tail, and no amount of extra state changes that.
When the algorithm flips a coinThe tie that breaks left
Two choices per key, the emptier bucket wins, and when the two are equally full a coin decides. Replace the coin with a rule — split the table into halves and always send a tie to the left one — and on a million keys the buckets holding three or more fall from 9,316 to 4,694, and the busiest bucket drops from four to three. The hashing, the probes and the keys are unchanged, and the rule spends no randomness at all.
CountingA worst case ten positions wide
Sorted input costs first-element quicksort 2,096,128 comparisons on 2,048 elements, 82 times its average. Reshuffle about eleven of the 2,048 positions and the cost halves — and it takes about ten at 128 elements, and between ten and thirteen at every size between. Reversed input costs insertion sort twice its average, and reshuffling half the positions still leaves 71% of the work. A worst case is a place in the space of inputs, and the two famous ones are places of very different sizes.
When the algorithm flips a coinChoices that are not independent
The power of two choices is analysed for choices drawn independently, and computing four independent hashes per key costs four hash evaluations. Compute two and take the choices to be h₁, h₁ + h₂, h₁ + 2h₂ and h₁ + 3h₂, and the choices are about as far from independent as they could be. On a million keys the buckets holding two or more come to 147,536 against 147,367 for four independent hashes, and the busiest bucket holds three either way.
When it does not fitWhat insurance against an estimate costs
A planner that trusts its row estimate expects to pay 1.057 times the better plan and risks 7.76. One that insures itself by halving its estimate before it decides expects 1.057 and risks 4.10 — the insurance is free. At a read ratio of sixteen the same insurance costs six per cent in expectation and makes the worst case worse. Whether a conservative planner is paying a sensible premium depends on two numbers the planner can measure and usually does not — its device's read ratio and the direction its own errors run.
One pass, and no roomThe window that is even in the wrong currency
A window of four thousand arrivals in eight blocks retires a block every 5.1 seconds on a steady stream and anywhere between 0.57 and 14.8 seconds on a stream whose rate moves. The structure cannot tell, because it is counting arrivals, and the alert written against it is in seconds.
The index that replaces the textWhat a ceiling costs in phrases
A cap of sixteen costs one phrase of a hundred and fifty-six and halves the worst chain. A cap of four costs six times the phrases. The curve between them is flat at one end and vertical at the other, and the elbow is where a structure should be built.
The floorsWork that falls as the answer grows
Output-sensitive usually means the cost rises with the answer instead of with the input. A descent over a document array costs five operations per document at an answer of seven and two at an answer of thirty-two, because the paths to many leaves share their tops.
The floorsProportional to the answer, not the alphabet
At a fixed alphabet of thirty-two, a loop costs three hundred and twenty ranks whether one symbol is present or all of them. The descent costs ten and sixty-two. The experiment has to move the answer without moving the alphabet, and the obvious sweep moves both.
When the algorithm is a tableA second try before any feature
A nearest-word search that learned one starting bound for a whole stream was proposed a bound for each query instead, read off features the search can compute before it walks. The proposed feature separates nothing: 58% of misspelt vocabulary words and 53% of words the vocabulary lacks begin with a real three-letter prefix. Length and unseen letter-triples do predict distance, and still buy about 1%, because the best start is two for almost every class. What closes half the gap to an oracle is a second cheap walk: one, then two, then discover.
When it does not fitWhat a planner pays to find out what to pay
Insurance against a row estimate is set from the error's median and spread, and a running system knows neither — it has to fit them from executed queries. Fitted from one query the divisor costs 1.263 times the better plan against 1.215 for a planner that never insures at all, so learning is worse than not learning until about sixteen queries have run. The tail, though, is bought immediately: one observation already holds the worst case to 24.7 against 36.6.
When the algorithm is a tableA checker that stops at two edits
A nearest-word search that must always answer pays most of its price on the queries whose answer is useless: misspellings of words the vocabulary does not have, whose nearest vocabulary word can be twenty edits away. Capping the answer at two edits keeps every suggestion a misspelt vocabulary word could get and costs 42% of the uncapped search. What it does not do is stop the false suggestions. It declines 95% of unfamiliar words of eleven letters or more and 1% of those of three or four, because two edits is most of a short word, and 72% of what it still says to an unfamiliar word is wrong — against 77% with no cap at all.
What is taught wronglyThe boundary that hides the burst
A window whose blocks hold five hundred and twelve arrivals reports a perfectly even stream — every block the same duration to the tick — while the arrivals it is retiring have an index of dispersion of 0.57. Move the block to a hundred and twenty-five and the same stream varies by 1.8 times.
One pass, and no roomThe moments past the second
Past the second moment no sign trick works, and the estimator that does — pick one position of the stream, count how often its key comes again, report m(r^k − (r − 1)^k) — is unbiased for every moment on every stream. Its variance can be computed exactly rather than sampled, and on real streams it is nowhere near its guarantee: 103 copies give F3 to ten per cent on a flat stream of 2,048 keys, and 2,630 on a moderately skewed one. The guarantee asks for 48,381, and it is not loose. One heavy key among 2,047 keys seen once needs 11,799.
When the algorithm is a tableThe triples a typo writes
A spelling checker capped at two edits keeps every correction it could make and still gives a false suggestion to 72% of the unfamiliar words it answers, because on short words distance cannot tell a typo of a vocabulary word from a word the vocabulary lacks. The query's letters were proposed as the second test: decline a query whose letter-triples the vocabulary has never seen. They cannot separate the two either. One edit writes about one unseen triple into any word, familiar or not, while an unfamiliar word brings 0.59 of its own, and two thirds bring none. Declining at two unseen triples removes a quarter of the false suggestions and costs half the corrections — twenty-two corrections for every false suggestion removed.
The floorsA result the size of its own noise
Sorting rotations by their first four characters beat the full Burrows–Wheeler transform by 0.022 bits a symbol. On sixteen streams of the same source the mean difference is 0.004 with a standard deviation of 0.011, and the short context is ahead on ten of them. The 1.2% was one draw. What survives is sharper than the result it replaces: from four characters upwards, every run break either rule makes is at a word boundary, and nothing above four characters decides anything at all.