Fields
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.
Counting
Comparisons, swaps, reads and writes are exactly countable and machine-independent. Every claim on this site starts by counting rather than by reading the code.
The floors
Some work cannot be avoided. The information-theoretic bound on comparison sorting is computable exactly, and the gap between it and each algorithm is a number.
What the machine does
The operation count is not the running time. Locality, cache lines and branch behaviour decide the constant, and they rank algorithms differently from the textbook count.
Structures
Heaps, trees, hash tables and dynamic arrays — each with its advertised bound put through the same measurement as everything else here.
Two parameters
A graph's cost is in V and E, so no bound here is a comparison until the density is stated. The same two algorithms change places when only the shape of the graph changes.
The other axis
Auxiliary space, counted at the point it is taken. "Sorts in place" turns out to cover three behaviours that differ by a factor of n, and one of them runs out of stack.
When the algorithm flips a coin
A skip list's shape is a sequence of coin flips rather than a property of its keys. Where the randomness is the structure rather than a rule applied to one, the distribution is the result and the average is the least of it.
What the libraries do
None of the sorts measured in the other fields is what runs when a program calls sort. A library sort is not an algorithm but a policy — a set of decisions, each with a threshold somebody typed — and the thresholds are where its behaviour actually lives.
When it does not fit
Every count in the other fields charges one for an array access, which is the right model for data in memory and the wrong one for data anywhere else. Here the unit of cost is the block, the model has two parameters that must be stated before anything is optimal, and the algorithms are the ones a database ships.
One pass, and no room
The data goes past once and there is not room to keep it. What survives is a summary of a few hundred bits, and the answer it gives is wrong — the whole design is a choice about how wrong, and every structure here buys accuracy with bits at a rate that can be measured.
The data that is not a number
A string comparison costs characters, and how many depends on what the two strings share. A symbol stream repeats, and repetition is the only thing any compressor has ever used. Both are invisible to a counter that charges one for a comparison, and both change which algorithm wins.
When the algorithm is a table
A dynamic program's cost is settled before its input is touched, by how many distinct subproblems its recurrence has. The unit is the subproblem; the second number is how many must be held at once; and the methods worth knowing are the ones that compute more in order to keep less.
The index that replaces the text
Every index measured here before this one was weighed at zero. A suffix array is four times the size of what it indexes and cannot answer without it; a compressed self-index is a third of it and hands the text back on request. The unit is the bit, the primitive is a rank on a bit vector rather than a comparison of two characters, and the text is taken away before any query is allowed to run.
What is taught wrongly
The comparisons that are made without units, the averages quoted without their distributions, and the bounds treated as predictions of speed.
A field is not a ladder
shelves and ideas are different things
A field is where an essay is shelved; an anchor is the idea it makes an argument about, and its rung is how deep that argument goes. Usually they agree. Where they do not, the field is the kind of question and the anchor is the subject — in place is a claim is filed under what is taught wrongly and sits on the space ladder, because its argument is a rung about auxiliary space and its subject is a phrase people repeat.
Every essay · Every ladder · The threads that cross fields · Every figure