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

Model — where it appears

The stated assumptions a bound was proved under — one pass, no deletions, unit costs, a random hash — every one of which can be turned into a dial. Every one of its assumptions can be turned into a dial, and each turn has a measurable consequence that the bound quoted under it does not describe.

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

stay 0.9, 400 pairsacgtacgt0525505225045240stay 0.5, 400 pairsacgtacgt0212202112022120cost of aligning the row letter with the column letterpseudocount 1

The matrix a corpus wrote

A substitution matrix is not a property of an alphabet. Fit one to four hundred pairs of sequences that rarely change and the dearest substitution costs five; fit the same model to four hundred pairs that often change and it costs two. Two hundred test pairs aligned under each matrix give different alignments in 115 cases — and a matrix fitted to eight pairs of the first kind moves 79 of them, from sampling alone.

tables · Cost above 0.01 of the stream · 13 really areone pass: 18 candidatestwo passes: 13 keys, exactly the heavy ones123456789101112131415161718128 counters · carry 1,376 bits5 of 18 spurious

The pass that was never a parameter

One pass is the streaming model's defining restriction, and the usual way to enforce it is to make a second read throw. A prohibition cannot be swept. Turn it into a dial and the first thing it says is that a second pass turns eighteen candidate heavy hitters, six of them wrong, into twelve that are exactly right — for 3,680 bits carried across the boundary and no extra space at all.

bounds · Pass 01234,09616K64K256K1.00M4.00Mmemory in 32-bit words, both buffers included (logarithmic)blocks moved ÷ blocks in the file3 passes2 passes1 passreread the file every passwrite the interval out everypass4,194,304 keys, block 1,024 wordstwo passes from 4,096 words

What a pass costs when it is a file

The streaming model trades passes for memory along n to the power one over p, and it never says what a pass costs. On a file a pass is a read of every block, and it cannot run in less than one block of memory. Charge both and the trade nearly disappears: the median of four million keys takes three passes at two blocks of memory and two passes at four, and writing the surviving interval out makes the third pass cost sixteen blocks instead of four thousand. On a heavy tail the same habit nearly doubles the bill.

bounds · Pass universe 0…11 · prefixes of 6 · candidate keeps 9 bitsthe two prefixes that collideA01234567891011B01234567891011first differencesame state — the candidate stores "7" after boththen both read the same suffix -1, -2, 12, 13, 14true median of A3true median of B4and one answer for both924 prefixes · floor ⌈log₂ C(12,6)⌉ = 10 bits10 bits collide on none

A floor one pass cannot get under

An exact one-pass selector must reach a different memory state for every prefix it might have read, and the pigeonhole that proves it is small enough to perform — nine hundred and twenty-four prefixes through a nine-bit state, the collision produced, the suffix that separates it, and two true medians it cannot both return. Ten bits collide on none, so the bound is exact — and a second pass walks under it by a factor of ninety.

floors · Pass 010020030040021φ 382φ 7203φ 17434φ 42885φ 1012486φ 242measured 409counts chargedlevel of the foldcharged at this levelrunning total64 shards · k = 32 · hashedcharged 409 · measured 409

The floor charged at every level

A key surviving a fold of sixty-four shards is charged 2, then 8, then 20, then 43, then 88, then 248 — the floor of whatever summary it was merged against, level by level. They sum to 409, and the damage read off the merged table is 409. The model that charged sixty-three copies of the leaf floor said 222.

floors · Floor 100100occurrences of the patternreadsmost frequent ", and " · 388 occurrencesthe scanthe chain12 documents · 144,617 characters3 of 6 won

What the generated collection was right about

Five strands of conclusions, drawn on collections made by one line with one dial, checked against a corpus nobody made. Most hold. One headline was a property of the generator's alphabet, and one crossing that was guessed at turns out to be met — but only with the structure the strand on range minima built.

practice · Document reads and writescache missesRadix sort, 8-bit digitsno comparisonsMerge sort965,752 comparisonsHeapsort1,895,405 comparisonsQuicksort, median-of-three1,187,435 comparisons65,536 keys of 32 bitsdark: the sort that compares nothing

The sort that makes none of them

Every count on this collection is a count of comparisons, swaps, reads or writes, and radix sort makes zero of the first. On 65,536 keys it moves five times less data than merge sort, misses the cache three times more, and sits 954,037 comparisons under the floor no comparison sort can go beneath — which is not an achievement, because the floor was never a statement about it.

counting · Count 01002003004005006007008009001000roundloads 1.0×blockedloads 1.0×hashedloads 17.6×worst error over the heaviest keyschaintreesmallest-firstlargest-first32 shards · k = 32 · 40,000 arrivalseven 1.00× · uneven 2.7×

A parameter that waits for another

Four merge fold shapes over thirty-two evenly loaded shards leave errors of 665, 667, 665 and 667 — a fifth of a per cent apart. Give the same four shapes shards whose loads span seventeen-fold and they leave 148, 183, 323 and 403. The parameter did nothing until a second parameter moved, and every measurement that fixed the second one saw nothing.

wrong · Merge 1.0%10.0%0.11fraction of characters changedper characterthe real runsthe real phrasesgenerated runsgenerated phrasesten revisions of one file · 24,580 characters2.32% against 3.24%

The dial that has no setting

The generator has one parameter. The real version history's run count asks it for 2.3% and its phrase count asks for 3.2% — and the reason is not that the dial is badly calibrated. Real edits average 7.3 characters a block and generated ones average 1.04.

wrong · Document 0.010.11101001000QuicksortQuicksortQuicksortShellsortHeapsortMerge sortMerge sort with a cutoffInsertion sortBubble sortSelection sortn²time × space, as a multiple of n²n = 8,192 · light: auxiliary slots · dark: the input counted toonone under n²

A floor under a product

Every lower bound written here so far puts a floor under one quantity. The published time–space bound for sorting puts one under a product: T·S is Ω(n²), so buying time with space and space with time cannot both be done. Measured, heapsort's product is 0.0028 n² — four hundred times under a bound nothing can beat. The bound is not wrong. It is stated in a model where the input may not be written, and every sort here writes to the input, which is where its working memory actually is.

bounds · Bound 12481632640.1110line size B, array elementstransfers × cells, per n²heapsortShellsortquicksort, random pivotquicksort, first pivotthe read-only familyn = 8,192, memory 512 cells, LRUrandom input

A product paid for in blocks

The published floor under sorting puts a bound on time times space, and a read-only family that scans its input over and over meets it, while every in-place sort sits far above it. Counted in block transfers rather than reads, the floor itself moves to n²/B: the family meets it at every block size, and so does every sort once memory holds the whole array. With a memory of 512 cells, quicksort sits a fixed eight times above the family at every block size, because partitioning is itself a scan. Only heapsort's distance grows with the block, from ten times at a line of one to 285 times at 64. The prediction that the family's lead would widen towards B holds against heapsort and nothing else.

bounds · Bound

Named alongside it

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

MeasurementHonest limitTrade offGuaranteeLower boundCorpusCost modelHeavy hitterMulti-passSpace time tradeState bitsStreaming model

All concepts