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

Precondition — where it appears

A condition a published bound was proved under, which remains necessary when the bound is quoted and is usually dropped along the way. A bound quoted without one is a bound about a different problem, and the failure it permits is quiet rather than a crash.

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

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 0%25%50%75%100%11.522.533.545what a matching character is worthreported as the shared region, of the longer sequencea random pair scores zero hereunit cost, alphabet acgtthe region found: 13 characters at the left, 34 at the right

The zero that moves the answer out of the corner

One extra term in the recurrence — a floor at zero — and the answer stops being in the last cell. It becomes a maximum over all 1,040 of them, the traceback's starting point is a search, and the whole mode is meaningless unless a randomly matched pair of characters scores negative on average. That last condition is on the scoring scheme, not on the sequences.

tables · Cost 10010³10³10⁴10⁵10⁶10⁷Vcounted workTopological order, one passDijkstra, binary heapBellman–Ford, all passesV from 64 to 2048, directed, acyclicwork = scans + visits + relaxations + queue comparisons

The precondition that removes the queue

Dijkstra maintains a priority queue to discover which vertex is safe to finalise next, and on a directed acyclic graph 65% of its counted work goes into that queue. The order it is discovering is already known. Relaxing in topological order makes exactly one relaxation per arc — 1,536 arcs, 1,536 relaxations — with no queue at all, and negative weights are fine.

graphs · Graph No estimate543 cells expanded · path 58Straight-line estimate325 cells expanded · path 58Estimate doubled71 cells expanded · path 64V = 900, E = 895, every edge costs onethe estimate is a function of the vertex, supplied by the caller

The precondition on a function the caller writes

Dijkstra expands 1,582 cells to find a path of 98 across a fifty-square grid. The same loop, with the straight-line distance to the goal added to each key, expands 405 and finds the same 98. The estimate has to be a function the caller supplies, and the guarantee holds only while that function never overestimates — a condition on somebody else's code, not on the graph.

graphs · Graph 10010³10³10⁴10⁵10⁶10⁷Vcounted workBreadth-firstDijkstra, binary heapBellman–FordBellman–Ford, all passesV from 64 to 2048, sparse, fixed average degreework = scans + visits + relaxations + queue comparisons

The bound with a precondition

Bellman–Ford is O(V·E), and on a graph of 2,048 vertices it stops after seven passes of the 2,047 the bound allows — a factor of 289 between the bound and the run. Dijkstra is faster and returns a wrong answer on four vertices if one arc is negative. Both facts are about the same clause: the qualifier at the end of the sentence.

graphs · Graph bits used · answers that were wrongBloom, bits cleared16,384 bits638 said no wrongly · 14 said yes wronglycounting, 4 bits a cell65,536 bits0 said no wrongly · 42 said yes wronglyfingerprints in two slots32,768 bits0 said no wrongly · 153 said yes wronglyand the condition on the caller1,000 deletions of keys never inserted lost 15 that were2,000 keys, 1,000 deleted, 20,000 absent keys querieda false negative is a different kind of wrong from a false positive

The evidence a filter cannot remove

A Bloom filter never says no about a key it holds, and that is its whole guarantee. Clear the bits of a thousand deleted keys and it starts saying no about 638 of the thousand it still holds. A counter in every cell repairs it at four times the space; a fingerprint repairs it at twice, and acquires a condition on the caller that neither of the others has.

randomness · Randomness Count-Min8,192 bitsCount-Sketch8,192 bitstug-of-war, F22,560 bitsGreenwald–Khanna0 bitsexponential histogram0 bitscash register+strict turnstile±general turnstile± may go negativesliding window+ expiresdeclareddeclared93% under—declareddeclareddeclared—declareddeclareddeclared—declared——————declared40,000 updates · deletion rate 0.5 · every count exact1,758 of 1,895 under

The model a bound was quoted in

Every accuracy figure in this field's first phase was measured under four unstated assumptions. Remove them one at a time and one structure loses its guarantee on 91% of queries, another's error stops falling when it is given more state, and a third has nothing to do at all.

bounds · Bound 0.1250.30.50.70.80.90.99probability of the dominant symbolbits per symbol0.01.63.2one bit per symbolHuffmanArithmeticEntropy H₀model: order 0 · 16,384 symbols per point8.7× at p = 0.99

The optimal code that is beaten

Huffman's code is optimal, the proof is correct, and on a stream where one symbol arrives 99 times in a hundred it spends 1.030 bits per symbol against an arithmetic coder's 0.119. Both facts hold. The word "optimal" in the theorem has a precondition attached that almost nobody quotes with it, and everything interesting about coding lives on the other side of that precondition.

wrong · Bits cells expandedNo estimate543 expanded · path 58Straight-line estimate325 expanded · path 58Dijkstra, reduced costs325 expanded · path 58 · 0 arcs priced below zeroV = 900, unit steps, seed 20260910shortest path 58

An estimate is a reweighting

Reprice every arc by the estimate's drop across it and run plain Dijkstra, and it expands the same 325 cells A* does, in the same order, because the two are one algorithm. Replace the estimate with one that is still never too high but drops too fast between neighbours, and 215 arcs go below zero — and on a stated grid the search that refuses to reopen a finished cell returns a path of 178 where the shortest is 169.

graphs · Graph Count-Min 4×64exact184 under16 overrms 42Count-Sketch 4×64-174-8708717499 under101 overrms 13general turnstile · insertions and deletions, counts may go negative · counts exact8,192 bits each

When the stream takes it back

Count-Min's estimate is never below the truth. That is a theorem about a stream where every update adds — and allow deletions that can take a count below zero and it comes back under on 93% of queries, with nothing in the number to say so.

wrong · Sketch

Named alongside it

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

Dijkstra's algorithmGuaranteeFailure modeHonest limitNegative weightRelaxationShortest pathAdmissibilityBellman–FordCancellationCost modelCounted primitive

All concepts