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

Worst case guarantee — where it appears

A bound holding on every input, including one an attacker chose, and which on the inputs an algorithm usually sees is often worth very little. It is the only kind of promise an adversary cannot invalidate, and the reason so many practical algorithms carry a fallback they almost never enter.

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

characters examinedNaive scan520,25663.51 per text characterKnuth–Morris–Pratt16,3211.99 per text characterBoyer–Moore–Horspool8,1290.99 per text characterRabin–Karp00.00 per text characterone unit = one character comparisonone matcher read no characters at all

The shift the pattern already knows

On a text of 8,192 characters the naive scan examines 520,256 of them and Knuth–Morris–Pratt examines 16,321 — a factor of 32, and 16,321 is 99.6% of the 2n that no input can push it past. On ordinary random text the same two algorithms examine 20,862 and 20,833. Both measurements are of the same pair of algorithms and only one of them is the reason anybody uses the second.

text · Symbol one read per text character24816326495alphabet size, m = 8characters read ÷ text length0.01.12.2Naive scanKnuth–Morris–PrattBoyer–Moore–Horspoolone unit = one character comparison · n = 20,000, m = 8Horspool's best here: 0.132 per character

The text that answers without reading it

Boyer–Moore–Horspool finds every occurrence of an eight-character pattern in a twenty-thousand-character text while examining 2,985 characters. Not 2,985 comparisons of eight characters each — 2,985 characters, 0.149 per character of text. It is a correct algorithm returning a complete answer about a text it has mostly not looked at, and the reason it can is a property of the alphabet rather than of the algorithm.

text · Symbol 0%25%50%75%100%0.20.30.40.450.50.550.60.70.8keys per slotconstructions that failedconstructions that faileddisplacements, scaled to 36840 constructions per point, 256 slots per tablea lookup is two probes, whatever the keys are

An 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.

randomness · Randomness answered 19.90%25%50%75%100%0.36420.52,170value, logarithmicfraction of the stream at or belowrank ±2%value 19.3–21.9answered 2.9% out20,000 values · log-normal, σ = 1.2 — a latency distribution · Greenwald–Khanna, ε = 0.02rank 1.02% · value 2.9%

The error that is on the rank

A summary of 77 tuples answers eight quantiles of a stream of 20,000 values, and every answer is guaranteed to sit within 0.9% of the stream from where it was asked for. The guarantee is deterministic, it holds on every distribution, and it is not about the numbers it returns.

streaming · Rank SETHno algorithm for k-SAT beats exhaustive search for every korthogonal vectorsno N^(2-e) algorithmedit distanceno n^(2-e) algorithmperformed heresplit and list, checked on 55,754 formulasquoted, not performed herequoted, not performed heresolid: an implication performed here · dashed: one that is quoteda conditional floor

A floor that holds if something else does

The four lower bounds on this site are proofs. This one is a chain of implications with a conjecture at the top, and neither end of it is proved. The link that can be performed is performed here — checked over 55,754 formulas, 918 of them unsatisfiable — and the link that cannot is quoted and marked as quoted.

floors · Bound 0%25%50%75%100%0.30.40.50.60.70.80.850.90.95keys per slotconstructions that failed2 hashes, 1 slot3 hashes, 1 slot2 hashes, 2 slots2 hashes, 4 slots20 constructions a point, 256 bucketsa lookup reads hashes × slots, whatever the keys

More hashes or wider buckets

A cuckoo table with two hash functions and one slot per bucket cannot be built past about half full. Give it a third hash function and it builds to 0.92. Keep two hashes and give each bucket two slots and it builds to 0.89; four slots, past 0.95. Every shape keeps the worst-case lookup the plain table was built for, and every shape pays for its threshold in a different place.

randomness · Randomness answered 4,1900%25%50%75%100%11.794,190value, logarithmicfraction of the stream at or belowrank ±2%value 24.9–4,190answered 1553.5% out20,000 values · Pareto, α = 1.2 — a heavy tail · Greenwald–Khanna, ε = 0.02rank 0.10% · value 1553.5%

A promise about the rank is not a promise about the value

A quantile summary asked for the 99th percentile of a log-normal stream returns the largest value it ever saw — 2,169 against a true 318, six times too high — and its rank error is 1.00% against a promised 2%. The guarantee held. It was never about the number.

wrong · Rank unit cost — triples broken0.02%unit cost — pivot bound failed0.02%log-odds on a keyboard walk — triples broken6.61%log-odds on a keyboard walk — pivot bound failed13.22%42,840 triples per model, enumerated0.02% shown where the true rate is zero

A distance that is not a distance

Under unit cost the edit distance obeys the triangle inequality and this site asserts that it does. Under a stated substitution matrix it need not, and on 42,840 enumerated triples it fails 2,832 times — taking with it every structure that prunes by distance, at a measured 13.22% of the bounds they rely on.

wrong · Cost linear probingchainedcuckoo, two tables0240.10.20.30.40.50.60.70.80.9load factorentries read per lookup0120.10.20.30.40.50.60.70.80.9load factorcache misses per lookup8,192 slots, 64 cache lines of 8a probe is an entry read; a miss is a line fetched

Two probes are two misses

Cuckoo hashing's lookup reads at most two slots, and at a load of 0.45 it reads 1.27 on average where linear probing reads 1.39. Replayed through a cache, it misses 1.18 times a lookup where linear probing misses 0.98. The table that wins the count the analysis uses loses the count the machine charges, because two slots in unrelated places are two cache lines, and a run of adjacent slots is usually one.

machine · Machine linear probingcuckoo, two tablescuckoo, buckets of 8024680.30.450.60.750.850.95load factorentries read per lookup00.511.50.30.450.60.750.850.95load factorcache misses per lookup8,192 slots, 64 cache lines of 8a probe is an entry read; a miss is a line fetched

The bucket that fits a line

Make each of a cuckoo table's two candidates a bucket of eight slots laid out on one cache line, and no lookup ever touches more than two lines, the table builds past a load of 0.95, and at that load it misses 1.21 times a lookup where linear probing misses 1.79. The prediction that it would lose to linear probing at low loads was wrong — it misses less at every load measured, 0.94 against 0.96 at 0.3 — because a key it holds almost never lives in its second bucket. The guarantee belongs to the alignment, not the bucket; eight slots on lines of four put a lookup on four lines.

machine · Machine

Named alongside it

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

Cuckoo hashingHash tableLoad factorFailure modeHonest limitMeasurementTail latencyTrade offAlphabet sizeCacheChained hashingCharacter comparison

All concepts