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.

 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

Exact selection against a file of 4,194,304 keys in 1,024-word blocks, charged in block transfers with the read buffer counted as memory: where the state law n^(1/p) falls under one block, passes and transfers across memory from two blocks to the whole file, rereading against writing the interval out, the heavy tail where writing out costs more than it saves, a rule that decides from the counts, and both cutting rules on three inputs.

 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.

 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

The time–space product of ten sorts, counted as peak auxiliary slots and again as the published bound counts it, against a family built to inhabit the model the bound is proved in: a read-only input, a write-only output, S cells between them, and a product of exactly n²(1 + 3/S).

 020405101520queries answeredfile-equivalents read and written, in allevery query from nothingthe counts keptparts of equal widthparts the counts balanceuniform keys, 2²² keys, 8K wordsevery answer checked against a sort

A file written once for the queries after

A sequence of 23 exact selection queries against a file of 2^22 keys in 1,024-word blocks, charged in block transfers: answering each from nothing, keeping the first query's counts, writing the file into parts of equal width during the first pass, and writing it into parts the counts balance — the cumulative cost, the query at which each starts to pay, what one later query costs as memory grows, why a pass writes far fewer parts than it counts, and uniform keys against a Pareto tail.

 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 time–space product of sorting, T·S with S counted as the published bound counts it, recomputed with T in block transfers — each sort's own access trace replayed through an LRU memory of M cells in lines of B — for heapsort, three quicksorts, Shellsort and the read-only family that meets the bound: the product against B, transfers per access, the product against the memory, each sort's distance from the family against n, and the order of the sorts under each accounting.

 50%30%10%3%1%0.050.10.20.512share of queries outside the top 2% of rankscost over parts balanced by keysbalanced by past queriessize × queries equal(∫√q)², predictedseven parts, fifty past queriesdotted: parts balanced by keys

Parts cut where the questions are

Selection queries against a file of 2^22 keys in blocks of 1,024 words, answered from one of seven parts written after a stated number of queries, with every block transfer charged by exact selection within the part: where each rule cuts, the cost a later query against the concentration of the workload beside the square-root prediction, against the number of past queries the cut was fitted to on uniform and heavy-tailed keys, and against how far the workload moves after the cut.

 0.020.050.10.20.530050010³10³drift, percentiles every 100 queriestransfers a querya band that never moves, 356best fixed interval, chosenafterevery 1,000 queriesthe law, half-life 250the law, half-life 1,000four streams of 20,000 queries a speedrewrites included

A recut the law decides

A file of 2²² keys written as seven parts cut by the square-root law from recent selection queries, with 90% of the queries in a band 2% wide that drifts at 0.02 to 0.5 percentiles every hundred queries or jumps every 1,000 to 10,000 queries, 20,000 queries a stream and four streams a setting, each query charged one or two reads of its part and each rewrite 8,192 transfers: recuts at fixed intervals of 125 to 4,000 queries against a recut the law triggers from a decayed density, cost against speed, the fixed intervals' curves, the law's ratio at four half-lives, jumps, one fast stream block by block, and where the cost goes.

 0%25%50%75%100%05,00010,00015,00020,000queriesrank in the filethe band's centrethe six cutsone stream, drift 0.1a cut is drawn at each recut

Every cut the law moves

A file of 2²² keys in seven parts cut by the square-root law from a decayed density of recent selection queries, recut when the law's saving pays, on queries whose hot band drifts at 0.02 to 0.5 percentiles every hundred queries or jumps every 1,000 to 10,000, four streams a setting: the cuts recut by recut on one stream, transfers a query for the law charged for the whole file, for the changed parts, with small moves held back and with only the parts around the band recut, against the best fixed interval; the share of the file and of the cuts each recut changes; the cost against how far a cut may move before it is moved; and jumps.

 the bandthe law, 7 partsthe band's part: 80169412601694169416907 by keys + band in 3 (9 parts)the band's part: 116117011706301172117011701170the law, 9 partsthe band's part: 681402140210241402140212526 by keys + band in 4 (9 parts)the band's part: 72136613649821366136413660%25%50%75%100%rank in the file; numbers are transfers a query in that part2^22 keys, blocks of 1,024a still band 2% wide

The two parts the law was not given

A file of 2²² keys queried in a band 2% wide that drifts at 0.02 to 0.5 percentiles every hundred queries or jumps every 1,000 to 10,000, recut under the square-root law's rule with a half-life of 250 queries and charged for the parts that change: the parts each design writes around one band; transfers a query against drift speed for the law in seven and nine parts and for backgrounds of seven, six, five and four parts by keys with the band's part cut in three or four; queries and rewrites at one speed; a still band at every centre; one drifting stream block by block; jumps; and the cost in the thousand queries after a jump.

All essays