Counterexample — where it appears
Named by 20 essays across 7 fields — each of them below, with the objects they name alongside it.
The 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.
A floor under a run count
A structure whose size is a function of the number of runs in a transform must give a different bit string to every text with that many runs, so it needs at least the logarithm of how many such texts there are. That count is walked rather than estimated — all four thousand and ninety-six of them — and the representation everybody uses turns out to have five bits of slack.
The invariant that was wrong for seven years
Timsort's merge policy is supposed to keep its run stack shallow, and the rule that enforces it inspects the top three entries. In 2015 a group of formal-methods researchers proved that the rule does not imply what it was believed to imply. Thirty-three elements are enough to break it, the array still comes out perfectly sorted, and the defect is in a structure that nothing about the output can show.
A function with r pieces
Computed at every one of eight thousand positions across four texts, a function defined on the whole suffix array agrees exactly with r−1 anchors and one addition. Anchor it at the successor instead of the predecessor — one character of code — and it disagrees at 506 of 800 positions while still returning plausible numbers.
An estimate is a reweighting
Reprice every arc by the estimate's drop across it and run plain Dijkstra, and it expands the same 325 cells A* does, in the same order, because the two are one algorithm. Replace the estimate with one that is still never too high but drops too fast between neighbours, and 215 arcs go below zero — and on a stated grid the search that refuses to reopen a finished cell returns a path of 178 where the shortest is 169.
Where 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.
A count over every input
Run five sorts on every one of the 40,320 orderings of eight elements and read off each one's best, mean and worst comparison count. Then mark where the inputs a benchmark generator names — sorted, reversed, nearly sorted, random, few unique — land. For merge sort, heapsort and quicksort with a median-of-three pivot, the worst case is an ordering none of them produces, and for the last of the three every named input lands on its best case.
The worst case found by climbing
A search that swaps two elements at a time and keeps whatever does not lower the count finds the worst case of all five sorts at eight elements, where every answer can be checked. At sixty-four it finds merge sort's worst case every time and reaches 39% of first-element quicksort's — whose worst case is sorted input, the most famous bad input there is. Checking a search where the answer is known certifies it only there.
The 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.
The case a failure link does not cover
Compute the exact good-suffix rule from the failure links alone and eighteen of twenty-two entries come out too large. The matcher then steps past sixty-six of two thousand and twenty-five occurrences, and every match it does report is a match.
Two structures that are one
Space-Saving never underestimates and Misra-Gries never overestimates, and they are taught as rival structures with opposite failure modes. Subtract one number from every Space-Saving counter and what is left is the Misra-Gries table, key for key and count for count, at all twenty thousand prefixes of a stream and at every table size tried.
A bound right for the wrong reason
Orient every edge of a graph towards its higher-degree endpoint and count triangles among out-neighbours, and the work is O(E·d), where d is the graph's degeneracy. The usual reason given is that the orientation keeps every out-degree at most d. On a graph of 1,024 vertices with degeneracy four, 136 vertices have more than four out-neighbours and one has seven. The bound survives by a different argument, and the orientation that does keep every out-degree at most d does less work.
The digest that promises nothing
The t-digest is the quantile structure most widely deployed and the only one with no proven bound on its rank error at any quantile. Measured, it beats the structure that does have one — and on two clusters with a gap between them it returns 431.5, where the data holds nothing at all between 40 and 800.
Two estimates that must agree
Run A* from both ends of a query at once, each search guided by its own straight-line estimate, and stop by the rule that is correct for two-ended Dijkstra. On 40 weighted grids it expands 1,002 cells on average and returns a longer path than the shortest on 12 of them. Give both searches one potential, half of one estimate minus half of the other, and the same rule is correct again — on all 40 grids, for 1,041 cells. Two estimates that measure different things cannot share a stopping rule until they are made to measure the same thing.
The sampler that cannot alias
A block window's boundary fires on an arrival count, and a stream whose burst repeats every sixty-four arrivals is reported as perfectly even by a block of five hundred and twelve. A quantile summary compresses on an update count, which is the same arrangement. Swept against three periodic value processes and their shuffles, it does not alias — and the reason is one line of arithmetic rather than a lucky sweep.
A parameter that waits for another
Four merge fold shapes over thirty-two evenly loaded shards leave errors of 665, 667, 665 and 667 — a fifth of a per cent apart. Give the same four shapes shards whose loads span seventeen-fold and they leave 148, 183, 323 and 403. The parameter did nothing until a second parameter moved, and every measurement that fixed the second one saw nothing.
The warning that is silent for the right reason
The statistic shipped to warn that a merge prediction is about to fail reads 0.160 on a stationary stream, 0.172 on a bursty one and 0.909 on a drifting one. It was asked to be looked at again because it does not catch a burst. It does not, and the reason is that on a burst there is nothing to catch.
The measure that cannot see the alphabet
Take a Fibonacci word of 4,181 characters and transform it with a before b — six runs. Transform the same word with b before a — nineteen. The parse gives eighteen phrases either way, and the gap between the two run counts grows with every word in the family.
The cap that binds on one text and not another
A periodic text looks like the one made of chains and pays 1.11 times the phrases for a cap of four. A text that repeats itself pays 2.96. The guess is backwards, and the reason is that depth measures nesting rather than repetition.
The pruning that loses an occurrence
Two versions of the same lower-bound pruning, each one character away from correct. Both return only real occurrences, both return fewer of them, and no check that asks whether the answers are right can tell either from the truth.
Named alongside it
The objects these essays reach for when they reach for this one.
MeasurementFalsificationGuaranteeVerificationFailure modeWorst caseAlphabetCompressibilityCorrectnessDijkstra's algorithmExhaustive searchHeuristic search