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

What a bound is

Asymptotic notation is a statement about a limit, not a measurement. Knowing precisely what it claims is the difference between using it and being misled by it.
10010³10010³10⁴10⁵10⁶ncomparisonsInsertionHeapsortMergeShellsorta power law is a straight line herecomparisons, counted exactly

What O-notation does not say

What asymptotic notation actually claims, the difference between O, Θ and Ω, why an O(n log n) algorithm can lose to an O(n²) one at every size anyone will ever run, and the four things the notation deliberately throws away.

 comparisons ÷ n log nMerge sort0.855Merge sort with a cutoff0.992Quicksort, random pivot1.018Quicksort, first-element1.082Quicksort, median of three1.117Shellsort1.246Heapsort1.649all of these fit n log n1.9× between best and worst

The constant the notation drops

How the constant factor in a complexity class is measured rather than estimated, why six linearithmic algorithms differ by a factor of two, and what the constant is and is not evidence about.

 -50%-40%-30%-20%-10%0%10%20%2561,0244,09616,384α = 0.5α = 0.8α = 0.9α = 0.95table size (slots)measured minus formula, relativemean of 6 fills per pointgreen band: within 5% of the formula

A limit is not a prediction

Why no finite set of measurements can establish an asymptotic claim, the case on this site where the fitted class genuinely changes when the range is extended, and how far a closed-form limit is from the finite object it describes.

 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

The difference between a guarantee averaged over an assumed distribution of inputs and a guarantee averaged over the algorithm's own coins, why the two are written with the same word, and what happens to each when somebody chooses the input.

 randomised pivot164 random bits2.96 ±23%median of mediansno random bits7.94 ±2%0.04.38.6comparisons per element — bar is the range over seeds, tick is the mean30 seeds, n = 4,001, median2.68× the mean, 14× the spread

What derandomising costs

Median-of-medians against a random pivot, measured over forty seeds, and the finding that derandomisation does not buy speed or safety in the class — it buys the disappearance of variance, and it is paid for in the mean.

 10³10³10⁴10⁵10⁶10⁷ncomparisonsadversary, no depth limitadversary, as it shipsrandom inputn²/2McIlroy's adversary, answering as it goescomparisons, counted exactly

The depth limit that almost never fires

What introsort's depth limit costs, how rarely it fires, and what it is worth against an adversary that decides the order of two elements at the moment it is asked.

 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

Four dials that separate the streaming models, the measured consequence of each, and the four distinct ways a correct bound gets quoted about something else.

 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

Making the number of passes a parameter — what crosses a boundary, why the carry has to be enforced rather than declared, and the exact answer a second read buys.

 0231436845165232shards mergedkeys whose count movedthree orders:folded in one at a timecombined pairwise, in a treefolded in, last shard firstMisra-Gries, k = 32 · hashedworst gap 298 arrivals

What a fold charges per level

Why a merge tree's depth rather than its width is what a counter table pays, why a chain costs a quantile summary less, and where the shape stops mattering at all.

 10010³10⁴10⁵errors allowed, kacts01234index walkthe whole table4,000 characters · m = 16 · 4 symbolscrossing at k = 4

The branches an error opens

How fast an index walk's cost grows per error allowed, why the factor falls rather than holding, and why a wider alphabet is not simply dearer.

 101001,00010010³10⁴10⁵characters of pattern in the setcomparisons before the scanboth rules, exactlybad character onlythe 1979 shift functionsfour symbols · patterns of 10137.35x at 128 patterns

The table that walks every pair

What each set of shift tables costs before the text is touched, why one construction is linear and the other is not, and what that does to the comparison between them.

 010010³10⁴interval extensions—48.1%68.5%69.8%errors allowed · share removed belowno pruningpruned on D4,000 characters · m = 1669.8% removed at k = 3

The branch that cannot reach an answer

What a lower-bound pruning removes from a bounded-error search tree, how the share moves with the budget and the alphabet, and where the crossing against the whole table ends up.

 good suffix, defined757,058good suffix, from links3,824bad character, defined12,666bad character, swept5,168128 patterns · 1,280 characters of patternfour symbols · m = 10198x and 2.5x

The case a failure link does not cover

The second case of the exact shift condition, what a construction that omits it produces, and why the omission is unsafe rather than merely inexact.

 10010100occurrences of the patternvisitsone visit an occurrencethe chainthe answer8 documents · m = 610 queries at every point

The cost that is the size of the answer

Muthukrishnan's chain of previous occurrences, what makes it proportional to the answer, and where its constant puts the crossing against a scan.

 10010100occurrences of the patternreadsthe scanchain, treechain, succinct8 documents · answer 8crossing 267 → 75

Where a crossing moved to

The output-sensitive document listing remeasured with the structure it is published with, what the crossing becomes, and what a prediction made from an asymptotic reading got wrong.

 11010³cap on the depthphrases9.8% more phrasesevery occurrence consideredthe earliest only4,096 charactersworst at cap 4

The cap an automaton cannot see

Why a linear-time construction enforces a different depth cap from an exhaustive one, what the difference costs, and the three regimes in which it costs nothing.

 051015510152025symbols in the alphabetfactor saved, and per cent paidranks saved, as a factorbits paid, per cent8,192 characters · 2 errorsx14.0 for 0.04%

A factor of fourteen, for four per cent

The operations saved and the bits paid, measured together across four alphabets, with the workload that decides whether the trade is worth taking.

 024bits a symbolequalzipftwoSizesoneLargeone bit a symbolentropyplain vectorscompressed blocks32 documents1.26x on the skewed collection

A code word is at least one bit

Where a frequency-shaped wavelet tree stops tracking the entropy, checked against Gallager's redundancy bound, and what gets underneath it.

 binary · sigma 22.00x2 against 4dna · sigma 42.67x6 against 16protein · sigma 204.76x42 against 200latin · sigma 264.81x54 against 26064-position interval2.00x to 4.81x

Two at binary, five at twenty-six

The interval enumeration measured across four alphabet sizes, and why a factor quoted from natural language is four times what a genomics workload will see.

 05e+31e+41.5e+40246bits kept in the low partbits⌊log₂(n/m)⌋ = 2low partshigh vector2,049 marks in 16,385 positions1 bits between the two roundings

The flat bottom of a shallow curve

How Elias–Fano's split is chosen, why the bottom of the cost curve is flat, and what that flatness excused for several strands.

 025507510000.50011.502errors permittedfactor against the published loop64.5%55.8%74.7%the walk: 11xthe descentthe label is the shareof dead extensions6 patterns · sigma 2198x to 105x

Flat in the budget, and not

Two operation savings swept over the error budget, what each one's shape says about its mechanism, and why the crossing between them is on a different axis entirely.

 110100k, the operators after the alternationstatesits DFA: 512its NFA: 30a literal's DFA: 11alphabet ab2^(k+1), exactly

The exponential is in the expression

The deterministic machine's size measured on two expression families, why the bound is met rather than approached, and what a state count quoted without its family says.

All essays