The thread: The check must reject
The argmin that cannot go backwards
The same triangular table, the same ninety-one cells, the same tree at the end of it — and 364 transitions one way against 156 the other. At 256 keys the ratio is 38. What removes the factor is not a property of the recurrence but a property of the numbers it is given, and the recurrence does not mention them.
When the algorithm is a tableThe edit that reaches back two rows
Swapping two adjacent characters is one keystroke and costs two edits. Adding it as a fourth transition is four lines, it is what nearly everything ships, and the function those four lines compute is not the one they are named after. Over 1,600 pairs of short strings the two definitions differ on twelve, and the shipped one breaks the triangle inequality on twelve triples where the other breaks it on none.
When it does not fitTwo ways to join, and the ratio that decides
The same join costs 260 transfers one way and 1,040 the other; at eight times the memory the same two costs are 2,880 and 1,280, the other way round. Neither number is a property of how large the tables are. The quantity that decides is how the smaller of them compares to memory, and a rule of thumb phrased in rows is a rule about somebody's machine.
CountingThe count that came from somewhere else
Every count in these essays is described as exact, reproducible, and identical on every machine. Two of them are not. A spanning-tree measurement quotes 42,385 comparisons spent in a sort, and that sort is the language's own — whose comparison count is specified nowhere, varies by a factor of thirteen across input kinds, and comes within one per cent of the information floor on random input.
Two parametersAn 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.
CountingA distribution computed rather than sampled
Quicksort with a random pivot makes a random number of comparisons, and every plate on this site reports one draw from that distribution. The distribution itself can be computed exactly — every pivot, every split, weighed — and on sixty-four elements its mean is 360.706 and its standard deviation 36.741. A hundred real runs average 365.98; two thousand average 360.74. The exact answer says how many runs a sample needs, and it is fewer as the input grows.
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.
CountingA 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.
CountingThe 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.
CountingThe sort whose count has no distribution
Batcher's network makes nineteen comparisons on every one of the 40,320 orderings of eight elements — sorted, reversed, adversarial or random — because it decides which pairs to compare before it sees any of them. That is two above merge sort's worst case and four below heapsort's best. At 65,536 elements the same refusal to adapt costs 4.07 times merge sort's worst case, and it buys three things no adaptive sort has, one of which is a proof of correctness that takes 65,536 inputs instead of twenty trillion.
The floorsFrom the right, two of sixteen
Run the same sweep in the opposite direction and every occurrence it produces lands behind its own cursor. It reports two of sixteen, every one of them genuinely there, and nothing about the answer says fourteen are missing.
Two parametersA 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.
Two parametersTwo 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.
CountingTwo floors that can be added
Handing back the ten smallest of 65,536 keys has two floors under it and neither is close where they cross — the larger of the two is 63,821 comparisons at k = 4,000 and the best method makes 125,401. They can be added, because a comparison that eliminates a key the caller never sees can never be a comparison that orders two the caller does see. Charged together the floor rises 62%, and the tournament goes from 1.97 times it to 1.21.
The floorsThe floor a merge cannot reach
Merging two sorted lists of five keys each has 252 possible outcomes, so counting says eight comparisons might do. Solving the game says nine are needed, and on equal lengths the shortfall keeps growing, as half the logarithm of the length. Averaged over random inputs, though, the same count is missed by a tenth of a comparison. The counting floor is nearly exact on average and wrong in the worst case.
The floorsThe order inside a tie
Sort the rotations of a text by their first four characters rather than by everything that follows, and the output clusters slightly better than the full Burrows–Wheeler transform: 1.780 bits a symbol against 1.802, from 63% of the character reads. It also costs nothing to undo. The prediction that a shorter context leaves ties for the inverse to pay for was wrong. The cost to undo comes from how a tie is ordered, not from how long the context is, and at k = 0 the wrong tie rule is exactly the sort.
When the algorithm flips a coinThe bits given to the wrong keys
A fingerprint table that gives later arrivals longer fingerprints holds 3.6% where a table that reserves nothing holds 21.1%, and it never runs out of reserve because it has none. It also dies at exactly the same size as the table that reserved nothing — 32 times its forecast, on the same key — because every generation shares one quotient, and the generation with the shortest fingerprint is the one that arrived first.
Two parametersA stop that is correct and never sooner
A two-ended search can stop when the two frontiers' keys together reach the best route found, and it can also stop when either frontier's own estimate reaches it alone. Both rules are safe, so a search may use whichever fires first. On forty weighted grids the second never fires: at the moment the first one stops the search, the larger of the two own-keys stands at 64% of the route. The extra rule costs 60% more counted work and a second priority queue to find that out.
CountingThe comparisons that name the answer
Returning the 4,000 smallest of 65,536 keys in order needs 61,536 comparisons to eliminate the rest and 42,100 to order the ones returned. That was the floor, 103,636, and a tournament made 125,388. What the floor never charged is saying which 4,000 come back. Charge that, and the floor is 125,341. On the same input the tournament is 47 comparisons above it, and for every k up to a hundred it is exactly on it.
When the algorithm flips a coinTwo blocks and the chances they add
Send each key to the emptier of two 512-bit blocks and the busiest block of a filter at sixteen bits a key holds 38 keys instead of 55. The false-positive rate does not move: 0.100% against 0.095%. At eight bits a key it doubles. A lookup cannot tell which block a key went to, so it has to ask both, and asking twice is two chances to be wrong. The repair that tames a hash table's worst bucket buys a filter nothing that a block twice as wide does not.
StructuresThe runs a permutation does not leave
A run of length L costs 2⌊log₂ L⌋ + 1 bits and replaces L, so coding runs pays above a mean run of six. This grid's mean run is 2.34, chance gives 1.90, and coding its runs makes it 17.8% larger.
The other axisAn index that cannot locate
Take an FM-index, remove the sampled positions and the bit vector marking them, and refuse every request for a position. What is left still counts, still extends intervals, still runs a whole search — and is a third smaller.
What is taught wronglyA schedule nobody writes down
A search scheme is valid when its searches between them cover every way the errors can fall — ten cases at two errors, enumerable in a line. A scheme missing one of them finds seven occurrences of eight, all real, at the right error counts, and reports nothing wrong.
What the machine doesA node costs two ranks
The left child's interval is the position minus the right child's. A descent that calls rank on both children returns exactly the same symbols at twice the cost, and nothing about the answer can see it.
StructuresA document already in the answer
The same walk, with the chain's test replaced by a lookup in the answer so far. It reports the same documents at the same cost, and two exchanged lines make it lose nine of seventeen without failing.
What is taught wronglyA saving quoted without its collection
A check asking whether a compressed document array is smaller than the plain one passes on the rounding whenever the document count is not a power of two. It would report a saving of nothing as sixteen per cent, on a collection that has no redundancy at all.
What is taught wronglyOne set, three orders
The symbols an interval holds do not depend on the tree's shape. The order they come out in does, and a search that accumulates a running count as it reads them computes a plausible number that is wrong on eighty per cent of queries.
What is taught wronglyA walk that does not prune
Remove the emptiness test and the descent visits every node of the tree, returns exactly the same symbols with exactly the same intervals, and costs sixty per cent more. No test of the answer can see it.
What is taught wronglyWhere the sparse representation loses
At every row marked, Elias–Fano costs twice the plain vector. The crossing is at one row in four, which is a sampling rate a real index uses — so the choice between the two is a choice, not an improvement.
What is taught wronglyA price with no structure under it
A class in this collection has charged Elias–Fano's price for several strands and stores an array of positions searched by binary search. The accounting is right about space to a bit per thousand and wrong about one operation by a factor of eight.