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

The thread: Measured, not assumed

A complexity class is usually read off the shape of the loops. Here it is fitted to counts taken across three orders of magnitude, and an algorithm is not given a class until the fit holds.
level 1level 2level 3level 4level 5key 21search: 8 comparisons, 3 hops26 keys, p = 0.5, seed 2026081057 coin flips decided the shape When the algorithm flips a coin

A structure made of coin flips

Insert the same 512 keys into a skip list twice, once sorted and once shuffled, from the same seed, and the two structures are identical — the same 11 levels, the same height for every key, the same silhouette. Nothing about the data reached the layout. The 1,064 coin flips did all of it.

 after 0 writes0 cmpafter 32 writes32 cmpafter 64 writes63 cmpafter 95 writes94 cmpafter 127 writes125 cmpafter 159 writes157 cmprandom input, seed stated in lib/count.js157 comparisons in this run Counting

Counting instead of timing

A stopwatch measures the laptop it runs on. A counter measures the algorithm. Every number on this site comes from an array that increments a tally each time it is read, written, compared or swapped — which makes the counts exact, reproducible to the last digit, and identical on every machine that has ever built this page.

 10010³10³10⁴10⁵10⁶10⁷Vcounted workBreadth-firstDijkstra, binary heapDijkstra, all V queuedBellman–Ford, all passesV from 64 to 2048, sparse, fixed average degreework = scans + visits + relaxations + queue comparisons Two parameters

Counting on a graph

An instrumented array counts comparisons, swaps, reads and writes, and none of those is what a graph algorithm spends its time on. Three new primitives are needed — an adjacency scanned, a vertex first reached, an edge relaxed — and once they exist, breadth-first and depth-first search turn out to be the same algorithm by every count kept on arrays.

 peak slots held at once, logarithmic18645124096Insertion sort11Selection sort11Bubble sort11Heapsort11Shellsort11Quicksort, median of three22log nQuicksort, random pivot28log nQuicksort, first-element29log nMerge sort with a cutoff4,106nMerge sort4,110nn = 4,096, random inputone slot = one array element or one stack frame The other axis

Measuring what an algorithm keeps

Four counters measure what an algorithm does and none of them measures what it holds. An in-place sort and an out-of-place one with identical comparison counts are different algorithms, and until this phase the site had no way to say so. Two primitives close the gap, and the second of them counts something no array counter can ever see.

 mean 494599th 60304,2825,4136,543comparisonsruns600 independent random inputs, n = 512worst run 1.32× the mean What is taught wrongly

The words "on average" are not a number

Quicksort is Θ(n log n) on average. Six hundred runs at n = 512 give a distribution with a mean of 4,945 comparisons, a median of 4,908, and a worst case 32% above the mean. The average is a summary of that picture, it is the least interesting thing in it, and it is almost always the only thing reported.

 1,00010,0000.1bits of state heldrelative errorHyperLogLog (-0.49)LogLog (-0.44)bottom-k (-0.38)50,000 distinct keys · 14 runs per point · truth counted exactlybest: 2.00% at 10,240 bits One pass, and no room

The answer that is allowed to be wrong

Every algorithm on this site so far was checked for correctness before it was measured. A summary of a stream cannot be — the data goes past once and does not fit — so the error becomes a resource, bought with bits, at an exchange rate that is a measurement.

 —bcab—abca6388328188632571322513518753111111one unit = one invocation of the recurrence481 calls, 25 distinct subproblems When the algorithm is a table

The cost is the number of subproblems

The edit-distance recurrence, written down literally, makes 29,737 calls on a six-letter word and a seven-letter word. Written down with a table beside it, it makes 56. Nothing about the arithmetic changed, and the class did.

 10⁵10⁶10³10⁴10⁵comparisonscache misses (modelled)Insertion sortSelection sortBubble sortMerge sortHeapsortQuicksort, firstQuicksort, median-3Quicksort, randomShellsortMerge + cutofffully associative · 64 lines × 8 elements · LRUa modelled count, not a time What the machine does

The count is not the time

An operation count is exact, machine-independent, and not a running time. The gap between them is mostly memory, and it is large enough to reorder the rankings. This site carries a second count — modelled cache misses from the same runs — and asserts that the two disagree, because if they agreed the second one would carry no information.

 every algorithm that makes at most 4 comparisonsthe 24 orderings of 4 elementsroot16 leaves16 seated · 8 with no leafone comparison per level, two outcomes per comparison⌈log₂(4!)⌉ = 5 comparisons The floors

The floor under every comparison sort

No algorithm that sorts by comparing pairs of elements can average fewer than log₂(n!) comparisons. Not one that exists, and not one that ever will. The argument takes three sentences, it is about counting leaves in a tree, and it is one of the few results in this subject that is genuinely about every possible algorithm rather than about a particular one.

 Timsort95,770shipsIntrosort130,863shipspdqsort114,408shipsDual-pivot116,836shipsMerge sort96,145textbookHeapsort187,796textbookQuicksort, median-3119,098textbookalgorithmcomparisonsrandom, n = 8,192comparisons, counted exactly What the libraries do

The sort the library ships

Every sorting algorithm measured on this site so far has one thing in common — none of them is what runs when a program calls sort. Python, Java, Rust and Android run Timsort; C++ runs introsort; Java's primitive sort is dual-pivot quicksort. Not one of the four was in this collection, and the reason it matters is that they are not algorithms in the sense the other essays use the word.

 one summary, k = 32769one summary, k = 25608 summaries of 32, merged536worst error over the top keys, in arrivalsconcentration 1.00 — the mean share of a heavy key held by one shard8 shards · hashed · balancedmerge 536 against matched 0 One pass, and no room

The state a merge is standing in for

A merge of eight summaries of thirty-two counters is wrong by 536 where one summary of thirty-two is wrong by 769, which reads as merging helping. One summary of two hundred and fifty-six counters — exactly what the eight were holding between them — is wrong by nothing at all.

 110100257amortised 2.000256512append numbercost of that append (log scale)growth factor 2, cost = 1 write + a copy of the array when it resizes9 resizes in 512 appends Structures

What amortised means

Appending to a dynamic array is O(1) amortised. It is also, on 512 appends, an operation that costs one unit 503 times and 257 units once. The amortised bound is a true statement about the sequence and a false one about any append in it, and the picture that shows why is a sawtooth nobody draws.

 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.

 0$abracadabra1a$abracadabr2abra$abracad3abracadabra$4acadabra$abr5adabra$abrac6bra$abracada7bracadabra$a8cadabra$abra9dabra$abraca10ra$abracadab11racadabra$aball 12 rotations of "abracadabra$", sorted0 character comparisons The index that replaces the text

A search that runs backwards

Twenty-three occurrences of a six-character pattern in sixteen thousand characters, found in twelve rank queries and zero character comparisons. Not few comparisons — none. The algorithm never asks whether two symbols are equal, and it knows how many matches there are before it has located one.

 0%25%50%75%12345×1.125×1.25×1.5×2×3×4capacity left unused at the endamortised cost per append20,000 appends, cost = 1 write + a copy on resizeneither end wins Structures

Choosing a growth factor

When a dynamic array fills up, how much bigger should the new one be? Doubling costs 2.02 units per append and leaves 39% of the allocation empty. Growing by an eighth costs 9.89 and leaves 10%. Every factor is a trade between time and space, no factor wins on both, and real implementations disagree about the answer for reasons that are measurable.

 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.

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

The constant the notation drops

Six algorithms on this site are Θ(n log n) and their comparison counts differ by a factor of two. The class is what they have in common; the constant is what distinguishes them. It is measurable to three digits, it is the number that actually decides between them, and it is precisely the number the classification is designed to discard.

 313roundconc 0.14536hashedconc 1.00309blockedconc 0.14how the arrivals were partitionedworst error over the top keysone summary, k = 32one summary, k = 256the merge of 8Space-Saving · stationary Zipf · 40,000 arrivals8 shards One pass, and no room

The partition the analysis did not mention

Space-Saving and Misra-Gries are the same structure under a stream, related by subtracting one number. Sharded eight ways and merged, one of them is wrong by 313 where the other is wrong by 927 — and swapping how the arrivals were assigned to machines reverses which is which.

 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.

 first-element pivot130,816 on sortedmedian of three5088 meanrandom pivot4937 meanblue bar: range over 400 random inputs · marker: the already-sorted inputn = 512a bad case that cannot be chosen is a different kind of bad case What is taught wrongly

What randomising the pivot buys

Quicksort taking the first element as its pivot costs 130,816 comparisons on an already sorted array of 512 — 27 times its cost on random data, and exactly the quadratic behaviour the algorithm exists to avoid. Randomising the pivot costs 5,490 on the same input. Randomisation does not make the bad case impossible; it makes it unchoosable.

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

 k/n = 0.1250.0810.1250.169position in the streamshare of runs in which it was sampledAlgorithm R, n = 32, k = 4, 40,000 runsworst departure 3.3% · noise 1.4% When the algorithm flips a coin

One pass, k slots, and two randomness budgets

Reservoir sampling takes a uniform sample of k items from a stream of unknown length in one pass and k slots. The textbook version and a second version draw from exactly the same distribution, and at 65,536 items one of them spends 1,356,399 random bits and the other spends 9,380.

 comparisonsswapsInsertion sort63,071 / 0Selection sort130,816 / 504Bubble sort129,688 / 62,563Merge sort3,964 / 0Heapsort7,653 / 4,170Quicksort5,049 / 2,380n = 512, random inputcounted in the same run Counting

One run, four counts, four answers

The question “how many operations” has no answer until the operation is named. Selection sort makes more comparisons than any other algorithm here and fewer writes than almost all of them; bubble sort matches its comparisons and does 124 times the swapping. The ranking depends entirely on which count is chosen, and the choice needs justifying.

 comparisons (bar length is log-scaled)sorting, floor43,250sorting, merge sort43,976searching, floor13searching, binary13searching, linear4,096green outline: a proved floor · blue: a measured run3,327× between the two floors The floors

The floor moves when the question does

Sorting 4,096 elements needs at least 43,250 comparisons. Finding one element among the same 4,096, already sorted, needs at least 13. The difference is a factor of 3,300 and it comes entirely from how many different answers the algorithm has to be able to give. A lower bound is a property of the question, not of any algorithm.

 a text that repeats itselfH0 4.01 · H3 0.236.291.48an order-1 sourceH0 3.00 · H3 0.895.151.67English-likeH0 3.89 · H3 0.976.162.25four symbols, uniformH0 2.00 · H3 1.994.102.59eight symbols, uniformH0 3.00 · H3 2.835.143.65bits per character of textupper bar: plain bit vectors · lower bar: compressed16,384 characters each · sample rate 64sigma 21, 8, 21, 4, 8 The index that replaces the text

The index that is smaller than the text

The Burrows–Wheeler transform is a permutation, so it changes no symbol frequency and a plain index over it is the same size whether the text has deep structure or none — 6.29 bits a character against 6.16, on texts whose third-order entropies differ fourfold. What the transform changed was the runs, and a structure that charges one bit per bit cannot see a run.

 keytruthfoldedtreereversed16,3626,8666,8696,86923,0743,5783,5813,58131,9632,4672,4702,47041,3731,9021,9071,95451,0981,6021,6051,60569351,5121,4711,46377691,2801,2851,30686561,1601,1631,16395661,1001,1011,095105101,0511,0361,029shaded rows are keys whose count depends on the order aloneSpace-Saving, k = 32 · 8 shards · hashed37 keys move with the order Structures

The order nobody fixed

The same eight summaries, combined pairwise in a tree or folded in one at a time, produce tables that differ on forty keys — the largest by 964 arrivals. Nothing in a deployment fixes which shape is used, and both answers are inside the guarantee.

 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.

 sorted insertion — height 62shuffled insertion — height 10truncated at depth 1663 keys, identical set, different arrival order62 deep against 10 Structures

The tree that is a list

A binary search tree gives logarithmic lookup. Build one from 128 keys in sorted order and it has height 127 — every node has one child, and a lookup is a linear scan. The failure is not gradual and it happens on the input people try first, which makes "O(log n) lookup" a claim about the insertion order rather than about the structure.

 adjacency scansrelaxationsqueue comparisonsvisitsBreadth-first14,336Dijkstra, all V queued2,118,656Dijkstra, binary heap56,973Bellman–Ford, all passes50,309,120Prim64,884Kruskal74,008V = 2048, E = 6,144, sparse, fixed average degreeevery segment counted exactly Two parameters

The queue decides the class, and the pseudocode does not name it

Dijkstra's algorithm is eleven lines of pseudocode with a priority queue in the middle of them. Which queue is not stated, and it is the difference between 56,973 units of work and 2,118,656 on the same graph. Two of the three queues here also fail to fit the class they are famous for, in a regime each.

All threads