Themes
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.
The constant is the content
Three sorts are all Θ(n log n) and their measured comparison counts differ by a factor of three. The class is what they have in common; the constant is what distinguishes them, and it is the part that gets dropped.
Two counts, two rankings
Comparisons are what textbooks count and cache misses are what the clock feels. They are independent, they rank algorithms differently, and the gap between them is where the practical knowledge lives.
There is a floor
Comparison sorting cannot use fewer than log₂(n!) comparisons, and that number is computable exactly. The distance between an algorithm and the floor is a measurement rather than a feeling.
Distributions, not averages
The expected cost of a randomised algorithm is the least interesting thing about it. What matters is how tightly the distribution concentrates, and that is what makes the bad cases stop mattering.
The figure is the run
Every trace here is a real execution and every number in its caption came from that same execution. A picture and its counts cannot disagree, because there is only one of them.
The structure decides the count
The same traversal over the same graph, laid out two ways, examines exactly the same edges and misses cache three and a half times as often. What an algorithm costs is decided as much by where its data is as by what it does.
Space is the other axis
Comparisons and cache misses are both proxies for duration. How much an algorithm keeps while it runs is a separate resource, it is measurable by the same discipline, and it is the one that decides whether a program runs at all.
In place is a claim
Three sorts described with the same two words hold one slot, twenty-two slots and four thousand slots at their peak. The phrase has no number in it, and once there is one, the algorithm most often called in-place turns out not to be.
The structure is a coin flip
A skip list's express lanes are not placed where the keys need them; they are placed where the coins fell, before a single key was compared. Build it twice and it is two different objects, so one build is an anecdote and the distribution over builds is the result.
Expected is not average
Average-case is a claim about the data and evaporates when somebody chooses the input. Expected-case is a claim about the algorithm's own coins and holds on every input there is. The two are written with the same word and only one of them survives an adversary.
Randomness is a resource
Comparisons, cache misses and slots are all counted here. Random bits are the fourth quantity, and two samplers that draw the same reservoir from the same distribution spend ten times different amounts of it — a difference no other counter on the site can see.
The threshold is the algorithm
A library sort's behaviour is decided by constants that appear in no complexity analysis: a minrun of 32, a cutoff of 16, a gallop threshold of 7. Each is one number in a real source file, each can be swept, and none of them is optimal for any single counter.
A branch is a cost
A processor executing a comparison does not wait to learn the answer; it guesses. A comparison whose outcome is predictable is nearly free and one that is a coin flip is not, and the two are the same comparison to every other counter here.
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.
The unit of cost is not one
Every count on this site charges one for an array access, and every real machine charges for a block. The same 65,536 accesses cost 1,024 transfers in one order and 65,536 in another, with nothing about the algorithm's work changed — which is the widest gap any two counters here have shown.
The model has parameters
In the external-memory model nothing is optimal until a block size and a memory size are named: the base of every logarithm is M/B, and an algorithm tuned for one block size is ordinary at another. The parameters are part of the claim rather than part of the hardware.
The floor depends on the model
log₂(n!) is a property of the sorting question and nothing moves it. The entropy floor is not like that: the same stream has one floor under a model of its symbols, a lower one under a model of its pairs, and a lower one still under a model of its four-grams. All of them are correct, and a compressor that beats one has not beaten Shannon — it has used a better model.
Compression is prediction
A coder spends −log₂ p bits on a symbol it thought had probability p, so the only way to spend fewer is to have expected the symbol more. Every compressor here is therefore a predictor wearing different clothes — a frequency table, a context, a window of recent text — and its bit count is the scorecard of how well it guessed.
The answer is an estimate
Every other algorithm here is checked for correctness before it is measured. A summary of a stream cannot be: the data goes past once and does not fit, so the answer is wrong and the design is a choice about how wrong. Accuracy becomes a resource bought with bits, at an exchange rate that is a measurement rather than a slogan.
A guarantee is not a result
"Accurate to within one per cent, with 99% confidence" is four separate claims, and three of them are usually dropped. Within one per cent of what — the item, or the whole stream? Confidence per query, or across all of them? The error a structure suffers and the error its bound promises are different quantities, and the gap between them is where the surprises live.
A guarantee names its model
Count-Min's estimate is never below the truth — in a stream where every update adds. Allow a count to go negative and the same structure comes back under on 91% of queries, with nothing in the number to say so.
Independence has a degree
"Assume a truly random hash" is where every sketch's analysis begins. What runs is a family with a degree, an estimator's mean and its variance spend different amounts of it, and the degree is enumerable.
The subproblem is the unit
A dynamic program is not a loop nest to be counted, it is a set of distinct subproblems and a number of transitions out of each. The same recurrence, written twice, is exponential once and linear once — and nothing about the arithmetic changed.
An index has a size
Every index on this site was weighed at zero until now. A suffix array is four times the text it indexes and cannot answer a single question without a copy of that text beside it; a compressed self-index is a third of the text and hands it back on request. The bits are the content.
The cost model is an input
Every edit distance on this site charges one for an insertion, one for a deletion and one for a substitution. That is a choice, it is rarely the right one, and it is the only choice under which the answer is a count of anything. Change it and the cheapest alignment moves.
The order is the algorithm
The recurrence is the easy half. Which cells are evaluated, in what order, and which are kept afterwards is where correctness and cost both live — and a table that cannot tell an unfilled cell from a cell holding zero reports neither.
A timestamp is state
A structure that has to forget needs to know when things happened, and knowing when costs bits. A windowed cardinality estimator spends more than half of itself on clocks — the one part of it no accuracy parameter touches, and the part that appears in none of its published sizes.
The error names its denominator
A rank error of a tenth of a per cent sounds small. At the 99.9th percentile it is the whole tail, and the value it returns is off by a factor of thirty-eight. The number did not change; the thing it was a fraction of did.
A pass is a resource
One pass is the streaming model's defining restriction, and a restriction cannot be swept. Make the number of passes a parameter and the space bound becomes a curve: exact selection needs the whole stream in one pass and three hundred bits in nine.
Repetition is not entropy
Two copies of a text have exactly the symbol statistics of one, so every entropy doubles when the second copy arrives and the second copy carries nothing. The number of runs in the transform is 224 at two copies and 224 at thirty-two — a measure of the sequence rather than of the distribution of its symbols.
The measure decides the structure
A compressed index is proportional to some measure of how much a text repeats itself — the runs in its transform, the phrases in its parse, an entropy. Which measure it is decides what the structure is small on, what a query costs against it, and whether relabelling the alphabet can change its size.
The definition is not the algorithm
A quantity written out as its own definition costs whatever quantifying over everything costs, and that number gets reported as a property of the quantity. The exact shift rules cost 137 times the published ones to build when built from the definition and 1.6 times when built from the trie's links — the same table, and the ratio was measuring an implementation.
A filter has a selectivity
A cheap stage that proposes candidates for an expensive one is worth having exactly when the candidates are few. That ratio decides everything and appears in no statement of any of these algorithms — and for seed-and-extend it can be computed, before the filter runs, from four numbers that are already known.
The check must reject
An assertion that has never rejected anything proves nothing, so every claim on this site is given a test it could fail — and the test is run against a deliberately broken version to confirm that it fires. A leftmost minimum where the rightmost is meant answers two ranges in five wrongly, with an index inside the range every time.
A model is not a corpus
A generated collection is an instrument: one dial, moved to produce a stated degree of repetition so a structure can be measured against it. It is not a sample. Its documents are one length, its edits one rate, its alphabet 22 symbols where real text has 87 — and a finding that turns on a threshold is a finding about where the data sits.