The thread: The constant is the content
An index larger than what it indexes
A suffix array over 16,384 characters is 229,376 bits, and it cannot answer a single question without the 81,920 bits of text beside it. Nearly four times the text, to search the text. Every index on this site had been weighed at zero until somebody put one on a scale.
What a bound isWhat 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.
StructuresChoosing 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.
The floorsHow close anything gets to the floor
The interesting question about a sorting algorithm is not its complexity class but its distance from the bound nothing can cross. Merge sort comes within 2.2% of the information-theoretic floor. Heapsort uses 96% more than it needs to. Selection sort uses nineteen times. Those three numbers say more than the classification does.
What a bound isThe 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.
What the libraries doWhen galloping pays
Timsort's merge does not always take elements one at a time. When one run has won seven times in a row it switches to searching for how many to take at once, and switches back when that stops paying. The mode saves 22,104 comparisons on nearly sorted input, 33,270 on input with few distinct values, and costs exactly six on random input — which is the whole design in three numbers.
Two parametersThe 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.
Two parametersThe 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.
The data that is not a numberThe shift a set of patterns allows
Aho-Corasick reads every character of the text exactly once, whatever the number of patterns. Commentz-Walter reads backwards inside a window and steps over what it can, and on eight patterns of ten characters it looks at sixty-two per cent of a twenty-thousand-character text. The rule that does the skipping is not the one everybody implements.
What the libraries doThe threshold somebody chose
A minrun of 32. An insertion cutoff of 16. A gallop threshold of 7. A depth limit of twice the logarithm. Four numbers, in four real source files, none of which appears in any complexity analysis — and each of which decides more about what these algorithms do than the analysis does. Swept, they turn out not to be optima, and finding out what they are instead is the point.
The data that is not a numberA distance that is a path through a grid
How far apart two strings are is a shortest-path problem on a grid whose every edge is drawn by the recurrence — and finding a string in a text costs 4,988 character comparisons where measuring how far it is from one costs 96,000.
The other axisThe alignment that fits in one line
Compute the table twice and hold three rows of it. The factor of two is a geometric series and is predicted exactly; measured, it comes down from 2.269 to 2.052 as the strings grow, and the peak is 3(m+1) cells on the nose.
The index that replaces the textThe sampling that goes the other way
An FM-index hands the text back, and the way it does it is to walk from the last character to the first. So thirty-two characters from the end cost thirty-three steps and thirty-two characters from the beginning cost eight thousand one hundred and ninety-two. The repair is a second array the same size as the first, indexed the other way round.
CountingTwo pivots and what they cost
Java changed its primitive sort in 2011 on the strength of an analysis showing dual-pivot quicksort does fewer comparisons than the classical one. It does. It also does nearly twice the swaps, and the analysis that decided the matter counted neither — it counted a weighted combination that had to be chosen before any conclusion could be drawn.
What the machine doesA column computed in machine words
Adjacent cells of a distance table differ by at most one, so a whole column is two bits per cell — and thirty-two of them fit in one register. Fifteen word operations per character replace three cell evaluations per cell, and below a pattern of fifteen characters the trade is a loss.
The other axisWhat 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.
What the machine doesRank is the only thing it does
Constant time and o(n) extra space — a phrase true of a rank directory costing 163% overhead and reading three words, and equally true of one costing 3% and reading eighteen. Both numbers are decided by two integers somebody typed into a header, and the phrase names neither.
What the machine doesSelect is not rank backwards
Rank counts the ones before a position and select finds the position of the k-th one, and only the first has an obvious structure. The constant-time answer costs 1.56 bits per one, is bounded in a unit the machine does not charge for, and on a vector with one bit in fifty it inspects more positions than the binary search it replaced.
The other axisWhat a second pass buys
Exact selection of a median from thirty-two thousand values needs the whole stream in one pass — a million bits — and eleven thousand in two. By nine passes it is three hundred and twenty. The state falls as n to the power one over p, which is a law with an exponent worth fitting, and on skewed data the deterministic rule misses it by three orders of magnitude.
The other axisWhat is still proportional to n
An index whose size is a function of the run count still has an n in it, and at thirty-two copies of a text the n is half of it. Everything that stores the transform grew by 45 per cent; the two arrays that answer "where" grew by eighteen times, and neither of them has anything to do with repetition.
What a bound isThe 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.
What the machine doesThe table that fits inside a block
A block of six parentheses has sixty-four possible shapes and twenty-eight questions can be asked about each, so all 1,792 answers fit in a table of 9,408 bits — computed once, shared by every structure of that block length, and never counted in any of their sizes.
Two parametersWhere two searches should stop
Search from both ends of a shortest-path query at once and the two frontiers meet somewhere in the middle, having expanded about two thirds of what one search would. Stop at the first vertex both searches have finished, and on five of forty weighted grids the path returned is longer than the shortest. The rule that is always right stops on a different condition, and on one of those grids it also stops sooner.
What a bound isThe 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.
What the libraries doThe rule that pays on a long enough text
With two patterns, the cheap tables cost 106 steps and the scan reads 13,084 characters; the exact tables cost 594 and the scan reads 12,306. Below thirty-two thousand characters the cheap tables win the total, above it the extra skipping pays for them, and with thirty-two patterns there is no crossing at all.
What is taught wronglyThe 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.
One pass, and no roomThe floor a histogram already knows
A summary of thirty-two counters settles at a smallest counter of 119, and the number can be computed from the shard's key frequencies before a single counter is allocated. The obvious way to compute it is wrong by a factor of two, and the reason is that the heavy counters carry no error at all.
The data that is not a numberThe shift somebody published
The exact rules for shifting a multi-pattern window are a definition that quantifies over every pattern at every offset. The 1979 rules are two tables read off the trie's own failure links, they are computed in one pass, and on this pattern set they agree with the definition at every node.
What a bound isThe 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.
StructuresThe counter that takes the smallest slot
Space-Saving keeps two numbers per key and they bracket the truth from both sides. On the twenty heaviest keys of a stream its mean error is a tenth of one arrival, against a hundred and ten for Misra-Gries at the same bits — and on the keys ranked past a hundred the ordering reverses.