What is taught wrongly
The words "on average" are not a number
Why an average-case complexity claim is a statement about a distribution, what the distribution behind randomised quicksort actually looks like, why the tail matters more than the mean in most systems, and three different things the word "average" is used for.
What randomising the pivot buys
What a randomised pivot actually guarantees, why average-case and expected-case are different claims, what median-of-three does and does not fix, and the input where no pivot rule helps at all.
The probe formula nobody checks
Knuth's linear-probing formula checked against tables actually filled, the finite-size error measured across table sizes and load factors, and the wrong-formula mistake that looks exactly like a broken hash function.
In place is a claim, and it is usually wrong about quicksort
What "sorts in place" turns out to mean once auxiliary space is counted rather than asserted, the input on which quicksort needs as much scratch as merge sort, and a space claim the fit refused.
The promise that does not survive the tree
What a quantile summary's error guarantee becomes when the summaries are merged, why the merged bound is a sum rather than a maximum, and how much space a merged summary fails to give back.
The block that is not a block
The external-memory model's honest limits — prefetching, concurrency, the hierarchy, read/write asymmetry and the replacement policy — and which of this field's claims survive each of them.
The formula everybody sizes filters with
The two approximations hidden in the Bloom filter sizing formula, which of them survives measurement, and why benchmarking a hashed structure on consecutive integers measures the wrong thing in a direction that is hard to guess.
The adversary who knows the seed
Why seeding a randomised algorithm deterministically for reproducibility removes the property the randomisation was for, how completely it removes it, and what to do about the tension.
The window that is not full
What happens to a space bound when the number of items in the window becomes a random variable — how far the occupancy swings on ordinary streams, and why sizing for the mean is undersizing by a factor of seven.
The invariant that was wrong for seven years
Constructing the smallest input that breaks Timsort's shipped merge invariant, and what it means that a correct sort can have a broken policy nothing observes.
The optimal code that is beaten
What Huffman's optimality theorem actually claims, why a prefix code cannot spend less than one bit on a symbol worth 0.152, and the two escapes — blocking symbols and abandoning symbol boundaries entirely.
The guarantee that is one query wide
The four separate claims inside every sketch guarantee, three of which are usually dropped — within epsilon of what, with what probability, per what, and measured against which stream.
A table wider than its input
What pseudo-polynomial means, why the encoding is part of the bound, and how rounding the values buys a table whose size no number in the input can move.
When the stream takes it back
The turnstile model, the strict turnstile that sits between it and the cash register, and what happens to a one-sided guarantee when the model it was proved in is left behind.
A promise about the rank is not a promise about the value
Rank error against value error, why the two coincide only on a uniform distribution, and the measured reversal in which the summary with the better guarantee returns the worse answers.
The ceiling the shortest pattern sets
Why Commentz-Walter's advantage is a property of the pattern set rather than of the algorithm — the ceiling, where it crosses the one-pass matcher, and the two counts that disagree about where.
The filter that proposes everything
Where a seed-and-extend filter stops paying — the two thresholds, the closed form the candidate count follows, and why a longer text does not dilute the problem.
A distance that is not a distance
Which of a metric's properties survive a substitution matrix and which does not, measured by enumeration, and what a pivot filter over a non-metric score silently gets wrong.
Two structures that are one
The Space-Saving and Misra-Gries summaries are the same state read two ways — the shift that converts one into the other, why it is k − 1 and not k, and what actually differs between them.
The digest that promises nothing
What a structure with no guarantee actually delivers — the arcsine scale, the accuracy that degrades towards the tail rather than improving, and an answer that never occurred in the data.
The histogram that cannot see the order
Where a merge-damage prediction computed from arrival frequencies breaks down, why a drifting distribution defeats it, and what a warning statistic can and cannot see.
The boundary that hides the burst
Why a block boundary that fires on an arrival count is a sampler, what it aliases against, and how a structure can report exactly nothing about a stream that is visibly uneven.
The sampler that cannot alias
Why a compression schedule cannot alias against a periodic stream even though a block boundary can, what separates the two, and how a negative result of this kind has to be checked.
A parameter that waits for another
Why a merge fold's shape is worth nothing under an even partition and a factor of 2.7 under an uneven one, and what that says about measuring one parameter at a time.
The half of a fall that is the logarithm
What a control does to a size sweep, why one measure of repetition carries a logarithm and the other does not, and how to tell which of your numbers is a property of your data.
The floor a merge does not settle at
Why a merged summary carries a lower floor than a fresh one over the same arrivals, the law that share follows, and how much of the merge prediction it recovers.
The warning that is silent for the right reason
Why a prediction's order-sensitivity warning is correctly silent on a bursty stream and on a large-shard failure, and what the second failure's own detector is.
A sampling that costs more than the array
Where a sampling proportional to the run count stops being an improvement, and why the condition is a property of the text rather than of the index.
The measure that cannot see the alphabet
Why the run count of a transform depends on which order the alphabet sorts in, why the phrase count cannot, and how large the difference gets.
The threshold that reaches zero
Where the counting filter stops filtering, why the collapse is exact rather than gradual, and how it differs from the seed filter's.
The deepest text is punctuation
What is actually at the bottom of a depth histogram's tail, why a run of one repeated character produces one level per character, and what that does to a cap chosen from the histogram.
Three savings in three currencies
Four methods for approximate matching, measured in the three resources they spend, and why there is no ordering between them.
What the approximation gives up
How far short of the exact shift the published rules fall, measured over their whole domain rather than over one run, and where the gap disappears.
The operations a candidate count leaves out
Why a plate counting candidates examined reports a range structure as two orders of magnitude better than it is, and what the comparison looks like in one currency.
The cap that binds on one text and not another
Why the cost of bounding a parse's copy depth is a threefold spread across four texts, and why the text that looks most like a chain is the cheapest to cap.
A sixth of what, exactly
The locating apparatus swept over the sampling rate, why half of it does not shrink at all, and what a size quoted for an index is actually a size of.
The pruning that loses an occurrence
Two ways to get a safe pruning wrong that return nothing but correct answers, and why a search's failures are invisible to every check except a comparison against exhaustion.
The ratio that was an implementation
How a comparison between two algorithms came to measure a definition against a rule, what the accounting error was, and what the number is once both halves are fixed.
The occurrences a join invents
What concatenating documents into one string invents, how many strings it invents, and what the two ways of stopping it cost.
A schedule nobody writes down
The covering condition that makes a list of searches a scheme, how a valid one was found by enumeration rather than quoted, and three ways of getting it wrong that produce plausible answers.
The level where compression stops paying
The per-level answer to a deferral, why an obvious optimisation is worth nothing here, and what a strand looks like when its result is that the idea was not worth having.
What a quadratic construction was setting
The depth-cap sweep re-run at the size a linear construction allows, which of its conclusions survive, and what it means that a measurement's size was chosen by its construction's cost.
The dial that has no setting
What happens when a one-parameter model of a repetitive collection is fitted to a real one, and the measurement of where the model is wrong.
A boundary that costs nothing
The expected cost of a document boundary on a repetitive collection, measured against its own control, and the ordering that came out backwards.
One copy per document is one occurrence per document
Occurrences per document measured in three collection shapes, and why repetition between documents cannot make a pattern dense inside one.
A saving quoted without its collection
The rejection test that keeps a compression figure honest, and the two collections it has to separate — one where the saving is real and one where it is a ceiling function.
One set, three orders
Why an interval enumeration's set is shape-independent and its order is not, and what a caller reading the output in sequence has to check.
A walk that does not prune
The rejection test for an operation whose entire content is a test, and the class of defect that only an operation count can catch.
Where the sparse representation loses
The two-ended measurement of a sparse bit-vector representation, the density at which it stops paying, and what a plate showing only the sparse end would report.
A price with no structure under it
A size model reported as a structure, the check that separates them, and why no measurement of bits could have found it.
Two factors that do not multiply
A product a reader computes without being told not to, drawn as a line the measurement falls short of, and the arithmetic of why.
A constant factor, not a term
A working-memory saving measured against the copy count, the retraction it produced, and what a query holds that no structure's accounting mentions.
A cache below the reachable set
What a bounded cache costs when a text reaches more states than it holds, and why the lazy construction defers an exponential rather than removing it.
The folklore is about a matcher
A backtracking matcher against Thompson's simulation on the standard witness, measured to the cap, and the claim the two are usually conflated into.