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 on this site 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 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.
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.
The data that is not a numberWhat repetition is worth once the logarithm is gone
On prose, nearly three quarters of the fall in phrases per character with size is arithmetic that any text pays. On a collection built of copies it is a fifth, and what is left is a factor of three that is genuinely the arrangement.
The data that is not a numberThe array is the length distribution
The document array holds each document once per character it contributed, so its symbol distribution is the collection's length distribution exactly. On equal-length documents its entropy is log d and no coding saves anything.
What is taught wronglyThe cap that binds on one text and not another
A periodic text looks like the one made of chains and pays 1.11 times the phrases for a cap of four. A text that repeats itself pays 2.96. The guess is backwards, and the reason is that depth measures nesting rather than repetition.
What a bound isFlat in the budget, and not
One saving is eleven times at every error budget, because it is a property of the alphabet. The other moves between ninety-eight and a hundred and five, because it follows the share of extensions that find nothing. Two savings, two shapes, and neither line crosses the other.
What is taught wronglyOne copy per document is one occurrence per document
The output-sensitive listing apparatus wins when a pattern occurs far more often than it occurs in documents. A collection of versions was supposed to be that case, and it is the one collection where the two numbers are equal by construction.