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

The thread: A limit is not a prediction

An asymptotic bound describes behaviour as n grows without end. It does not say which of two algorithms is faster at the size anyone will actually run, and treating it as though it does is the commonest error in the subject.
10010³10010³10⁴10⁵10⁶ncomparisonsInsertionHeapsortMergeShellsorta power law is a straight line herecomparisons, counted exactly What a bound is

What O-notation does not say

Big-O is a statement about a limit. It does not say how fast, it does not say which is better, it does not say anything at all about any particular n, and it discards precisely the factor that usually decides the answer. Knowing exactly what it claims is the difference between using it and being misled by it.

 11010010³10⁴10⁵10⁶10⁷natural runs r in the inputcomparisonsn / minrun = 256TimsortMerge sortInsertionn + n log₂ rn = 8,192, runs built exactlycomparisons, counted exactly What the libraries do

A run is a property of the input

A benchmark that says "nearly sorted" never says how nearly. It is a recipe with a seed, not a measurement, and an adaptive bound stated against it is a bound with an undefined second parameter. Counting the natural runs turns the shape of an input into a number — and then Timsort's bound becomes something that can be fitted rather than quoted.

 10010³10010³10⁴10⁵10⁶ncomparisonsInsertionMergeHeapsortQuicksorta power law is a straight line herecomparisons, counted exactly Counting

Fitting a class to measurements

A complexity class is normally read off the shape of the loops and written down. Here it is fitted to counts taken across three orders of magnitude, and an algorithm is granted a class only if the fit holds — which turns a statement about code into a statement that can fail.

 0%25%50%75%100%645124,09665,536cache holds 512array size n (elements)miss ratefully associative · 64 lines × 8 elements · LRU20,000 random accesses per point What the machine does

The cliff where the data stops fitting

Below the cache's capacity, almost every access hits. A factor of eight above it, almost every access misses. The transition is not gradual and it is not a property of any algorithm — it is a property of how much data there is, and an algorithm's complexity class says nothing about which side of it a program is working on.

 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 data that is not a number

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.

 sparse, fixed average degree10010³10³10⁴10⁵10⁶VworkDijkstra, binary heap — E log EDijkstra, all V queued — V^2dense, fixed density10010⁴10⁵VworkDijkstra, binary heap — V + EDijkstra, all V queued — Ethe class is a property of the sweep as much as of the algorithmwork = scans + visits + relaxations + queue comparisons Two parameters

Two parameters, one bound, no order

With one size parameter the candidate classes are ordered — n beats n log n beats n², always, and comparing two bounds is reading them. With two, E log V and V² have no order at all, and which one is smaller is a property of the graph. Sweeping V at fixed degree and at fixed density are different experiments, and the same algorithm fits different classes in the two.

 —abrocadabro—abracadabra012101221012210122112222123321233212332123321233212322one unit = one subproblem given a value54 of 144 cells, 90 skipped When the algorithm is a table

A band as wide as the answer

If two strings are close, the optimal route stays near the diagonal and nine cells in ten cannot be on it. A band of three finds the right answer on a pair 300 characters long — and a band of thirty-two is needed before anything can prove it.

 -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 What a bound is

A limit is not a prediction

Measured from n = 64 to n = 4,096, this site's hybrid merge sort fits a linear class better than n log n. Measured out to n = 65,536, the ranking reverses. Nothing changed but the range — and this is not a flaw in the method, it is the method finding the exact place where measurement stops being able to help.

 1234560.000.250.500.75formulameasuredload factor αprobes per insertion8,192 slots, mean of 8 fills, seeds stated in lib/structures.jstwo routes agree to 2.3% What is taught wrongly

The probe formula nobody checks

The expected number of probes to insert into a hash table under linear probing is ½(1 + 1/(1−α)²). It is quoted constantly, it is correct, and applied to a table of 256 slots at 95% load it overstates the measured cost by nearly half — because it is an asymptotic result and a real table is not asymptotic.

 10³10⁴10³10⁴10⁵ncomparisonsbottom-up (Floyd)repeated insertionn from 128 to 65,536, random input, seeded1.21× between the two at the right-hand edge Structures

Building a heap from the bottom

Bottom-up heap construction is Θ(n) and repeated insertion is Θ(n log n), and the second of those is a worst case quoted as a behaviour. On random input, repeated insertion measures linear too — 2.22 comparisons per element against 1.87 — and the famous logarithmic factor never appears. On ascending input it appears in full, and it is a factor of six.

 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 What a bound is

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.

 pale: total slots ever allocated · dark: peak held at onceone buffer, allocated once16,38416,400peak 100% of na buffer per merge229,37616,386peak 100% of nn = 16,384, random input208,687 comparisons each — identical in time The other axis

The space the model does not see

A slot is not a byte, a frame is not a slot, sixteen thousand allocations are not one allocation of the same size, and none of these numbers includes the input. The space counters are the newest instrument here and the honest account of what they miss is longer than the account of what they measure — including one bound this phase set out to demonstrate and could not.

 least recently usedthe offline optimumA loop over 7 blocks35 accesses35113.18×Random over 7 blocks35 accesses971.29×A straight sweep35 accesses35351.00×B = 8, M = 48 (M/B = 6)3.2× on the loop What is taught wrongly

The block that is not a block

This field's model has one memory, one block size, one processor, no prefetcher, no queue and no clock, and every number in it is a count of transfers rather than a duration. A real machine has five levels, reads ahead, issues a hundred requests at once, and charges four orders of magnitude more for one kind of transfer than another. What survives the difference is worth stating exactly, and so is what does not.

 busiest vertexuniform pairsbusiest 16 · Σd² 43,104 · degeneracy 4attachmentbusiest 114 · Σd² 90,296 · degeneracy 4pairs of neighbours examineduniform pairs — every pair18,480uniform pairs — oriented4,090attachment — every pair42,076attachment — oriented3,339V = 1,024, E = 3,072 on both30 triangles and 249 — the answers, which also differ Two parameters

Two parameters are not enough either

Two graphs on 1,024 vertices with 3,072 edges each — identical in both numbers every bound in this field is written in. Enumerating every pair of neighbours of every vertex costs 18,480 examinations on one and 42,076 on the other. The quantity that separates them is a third parameter, it is computable in linear time, and it appears in no statement of the problem.

 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 Two parameters

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.

 —gactacgat—gattacagt112223334244352461647one unit = one subproblem given a value21 matching pairs, 21% of the rectangle When the algorithm is a table

The cells that were never worth having

Two three-hundred-character strings over twenty-six letters give a table of 90,601 cells, and 3,421 of them are pairs of positions whose characters agree. Only those can lengthen anything. A method that enumerates exactly those computes a twenty-sixth of the table — and on a two-letter alphabet it computes half of it and is worse than the table it replaced.

 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 What a bound is

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.

 1,00010³window length W, in arrivalsbits of state heldW bits, exactε = 0.5ε = 0.2ε = 0.1ε = 0.05ε = 0.02sliding-window model · 40,000 arrivals · state from the shape of the structure5,670 bits at W = 8,000 The other axis

What a window costs in bits

The approximate structure grows like the square of a logarithm and the exact one grows like the window, so the approximation wins eventually. Eventually is a window of 6,000 at a 2% tolerance — and below it the summary is larger than the thing it is summarising.

 1101001,0000.111010010³true count of the keyrelative errorheaviest keyrarest key4×64 counters · 8,192 bits · Zipf s = 1.1 · 3,528 distinct keys at 702 positions4.11% to 34100% What is taught wrongly

The guarantee that is one query wide

A sketch described as accurate to within a per cent is accurate to within a per cent of the whole stream, not of the number asked about. On a skewed stream the same sketch is 4% wrong about its heaviest key and 34,100% wrong about one of its rarest, and both figures satisfy the bound.

 10³10⁴capacity Wsubproblems given a valueBottom-up table · 1.00Top-down, reachable only · 0.14one unit = one subproblem given a valuesubproblems given a value, W from 200 to 3200 What is taught wrongly

A table wider than its input

The knapsack table has (n+1)(W+1) cells and is called polynomial. Adding one character to the input doubles it — across four settings the table grows sixty-four times while the input it is written from grows by half.

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

The branches an error opens

The tree multiplies by 19.6 for the first error, 12.3 for the second, 10.3 for the third and 8.8 for the fourth. A branching factor of four on a sixteen-character pattern would predict sixty-four, and the gap between sixty-four and eight is the intervals emptying.

 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 When the algorithm flips a coin

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.

 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 What a bound is

The table that walks every pair

The exact shift rules cost 769,724 character comparisons to build for 128 patterns and the published ones cost 5,604. The scan they are both built for reads 41,580 characters, so one of the two constructions is eighteen times the work it is there to save.

 the same 16 patterns, one of them shortenedshortest 1658.4%mean shift 3.15shortest 1262.8%mean shift 2.99shortest 869.7%mean shift 2.64shortest 680.5%mean shift 2.35shortest 493.4%mean shift 1.98shortest 399.2%mean shift 1.71shortest 2100.0%mean shift 1.3716 patterns, 15 of them 16 characterstext 20,000 What is taught wrongly

The ceiling the shortest pattern sets

A matcher that skips is described as faster than one that reads every character, and the description leaves out what decides it. No shift can exceed the shortest pattern in the set, so adding one two-character pattern to fifteen of sixteen characters takes a run from reading fifty-eight per cent of the text to reading all of it twice.

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

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.

 1,00010,00010³10⁴characters of textsteps, precomputation plus scancrossing at 8,000published rulesexact rules2 patterns · four symbolscrossing 8,000 · was 32,000 What the libraries do

Where the exact rules pay now

With a construction as cheap as the published one, the exact shift rules pay for themselves past eight thousand characters of text at two patterns, four thousand at four, and never at thirty-two — because by thirty-two patterns the two rules make identical decisions.

 0.111010010³10³10⁴floor, in countsarrivals in the shard, nround-robin — n^1.02hashed — fit refusedresidual 2.7%slope 5.2 → 1.19k = 32 · 40,000 arrivalsthe table holds 1.33 of a hashed shard's keys and 0.01 of the stream's The floors

A floor with two variables in it

Under round-robin a Space-Saving summary's floor is 0.0203·n^1.018 over a hundred-and-twenty-eight-fold range of shard size, worst residual 2.7%. Under hashing the same measurement has no exponent at all — the local slope runs from n^5.17 to n^1.19 — and a least-squares line through it reports n^1.73 at a 441% residual.

 1,00010,00010phrases followed12481632characters in the collection · copies aboveworst depthmean depthEnglish-like · z = 156median 18 · 90th 31 The other axis

The character that costs a chain

The index over thirty-two copies is 8,892 bits and does not grow. Producing one character of the text it indexes costs 17.89 phrase-follows on average and 38 in the worst case, against 2.38 and 7 at one copy — the size stopped growing and the price of reading it did not.

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

The cost that is the size of the answer

Ten range-minimum queries answer the listing at every point of a sweep where the occurrences run from 30 to 790. They cost 256 to 288 node visits — and the scan they replace costs 30 to 790, so the output-sensitive method loses until about thirty occurrences per document.

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

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.

All threads