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

Amortised analysis — where it appears

An accounting of cost across a sequence of operations, in which an occasional expensive step is paid for by the cheap ones that made it necessary. It says nothing about any individual operation, which matters wherever the slow step's latency is what a service objective is written about.

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

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

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.

structures · Structure 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

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.

structures · Structure 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 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.

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

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.

structures · 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

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.

graphs · Graph 10³10⁴11010010³npointer hops per findneitherpath compressionunion by rankboth3n random unions, seededα(n) ≤ 4 for every n on this axis

The constant that is practically constant

Everywhere else on this site the class is honest and the constant is hiding something. Union–find is the exact inverse — its bound is formally not constant, its growth term reaches four at n = 2,048 and stays there for every input anyone will ever run, and the measured path length is flat at 0.92 pointer hops across a two-hundred-fold range of n.

graphs · Graph 1100ε — the exponent the fanout is B toelements written per key33445679ε = 1 — the B-tree ·fanout 256 · 3transfers a queryε = 0.5 · fanout 16 · 5a querythe number above eachpoint is what a querycostsB = 256, M = 16,384 (M/B = 64)131,072 random keys

One dial between two structures

A B-tree writes 226 elements of block for every key stored and a log-structured store writes two. They are presented as rival designs. They are one design at two settings of an exponent that nothing in either description mentions, and every setting between them is available.

applied · Transfer roothseirhesssolid: a transition on a character · dashed: a suffix or failure link10 states for 12 pattern characters

One pass for every pattern at once

Sixty-four patterns, one text, twenty thousand characters read. Running this site's KMP once per pattern reads 1,595,445 — and an implementation missing one kind of link finds fewer occurrences, reads exactly as much, and looks better on every counter.

text · Automaton 3,600 — the window opens4,000 — now32161616884the window edge215 in buckets−16 for the oldest= 200true 2000.3% outsliding-window model · ε = 0.2, k = 5 · 1,764 merges406 bits against 400

The summary that has to forget

Every structure in this field so far accumulates. Ask instead for the count over only the last thousand arrivals and no counter will do, because a counter has no record of which of its increments are old — and the repair is a row of buckets whose whole error is the oldest one.

streaming · Window 11010010⁴10⁵queries answeredcharacter comparisons, cumulative5 queriesScan each timeIndex, then queryone unit = one character comparison · 4 doubling roundsbreak-even at 5 queries

The index that is the text

A suffix array sorts all 4,097 suffixes of a text — 8.4 million characters of string, in total — and examines exactly zero characters doing it. It then answers a search in 91 characters where a scan costs 1,472, and the whole thing pays for itself at six queries. Both halves of that are worth the same amount of attention, and the first is the one that is usually skipped.

structures · Symbol —1234152abcbcbccbsolid: a transition on a character · dashed: a suffix or failure link8 states ≤ 9, 9 transitions ≤ 11

Every substring, in fewer states than substrings

A text of 512 characters has 129,416 distinct substrings. A machine that recognises every one of them, and nothing else, needs 831 states — and the bound it is under, 2n − 1, is reached exactly by a string one line long.

structures · Automaton 10010³10⁴10⁵10⁶⌊1/2ε⌋ = 50151025501002005001,000tuples, and tuples examinedcompression period, in updatestuples examinedpeak tuplesresident tuplesworst rank errorε = 0.01 · 20,000 arrivalspeak 10× · work 72× · answer 1.21×

The period that is not a promise

Greenwald–Khanna's ε appears twice — once as the rank tolerance the structure promises, and once as ⌊1/2ε⌋, the number of updates between compressions. Unhook the second from the first and sweep it across a thousand-fold range. The tuples held move by 10%, the worst rank error by 21%, the peak by ten times and the housekeeping by seventy.

streaming · Rank

Named alongside it

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

Worst caseCharacter comparisonGuaranteeTrade offAlphabetAutomatonBinary searchFailure functionHeapIndexMeasured countMeasurement

All concepts