Lower bound — where it appears
Named by 41 essays across 9 fields — each of them below, with the objects they name alongside it.
The floor under every comparison sort
No algorithm that sorts by comparing pairs of elements can average fewer than log₂(n!) comparisons. Not one that exists, and not one that ever will. The argument takes three sentences, it is about counting leaves in a tree, and it is one of the few results in this subject that is genuinely about every possible algorithm rather than about a particular one.
How close anything gets to the floor
The interesting question about a sorting algorithm is not its complexity class but its distance from the bound nothing can cross. Merge sort comes within 2.2% of the information-theoretic floor. Heapsort uses 96% more than it needs to. Selection sort uses nineteen times. Those three numbers say more than the classification does.
The floor moves when the question does
Sorting 4,096 elements needs at least 43,250 comparisons. Finding one element among the same 4,096, already sorted, needs at least 13. The difference is a factor of 3,300 and it comes entirely from how many different answers the algorithm has to be able to give. A lower bound is a property of the question, not of any algorithm.
The text that answers without reading it
Boyer–Moore–Horspool finds every occurrence of an eight-character pattern in a twenty-thousand-character text while examining 2,985 characters. Not 2,985 comparisons of eight characters each — 2,985 characters, 0.149 per character of text. It is a correct algorithm returning a complete answer about a text it has mostly not looked at, and the reason it can is a property of the alphabet rather than of the algorithm.
The adversary who hides the edge
The floor under comparison sorting comes from counting outputs — n! of them, so log₂(n!) comparisons. Connectivity has two outputs, so the same argument gives a floor of one comparison, which is useless. A different kind of argument gives Ω(E), and having both on the site is the point: lower bounds are not one technique.
The floor when the values repeat
log₂(n!) counts orderings of distinguishable things. Two hundred and fifty-six values drawn from eight distinct ones have 1,684 bits of permutation entropy and 739 bits of distinguishability, so the real floor is less than half the one every table quotes — and merge sort, which sits exactly on the quoted floor, is 2.3 times above the one that applies.
A floor on the bits
Answering membership for n keys with a false-positive rate of 1% and no false negatives requires at least 6.64 bits per key, whatever the structure. A Bloom filter uses 9.59. The gap is 44.27% at that rate and at every other rate, and it is the first bound on this site that a real structure comes close to.
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 floor under moving data
The information-theoretic floor for comparison sorting is log₂(n!) and it says nothing about a file on a disk. In the external model the floor is (n/B)·log_{M/B}(n/B), it is a bound on every algorithm rather than on merge sorts, and a measured external sort sits 2.40 to 2.97 times above it. Both numbers are computable, and the gap between them is what a real implementation costs.
What a reordering costs to undo
Sorting the characters of a text clusters them perfectly: a move-to-front pass then leaves 289 bits where the text's own floor is 31,931. Naming which arrangement of those characters the text was costs 31,827 bits, and the two numbers add to the floor it started from. The Burrows–Wheeler transform clusters less and costs nothing to undo, which is the only reason it is the one that is used.
The model a bound was quoted in
Every accuracy figure in this field's first phase was measured under four unstated assumptions. Remove them one at a time and one structure loses its guarantee on 91% of queries, another's error stops falling when it is given more state, and a third has nothing to do at all.
Permuting is the harder problem here
Rearranging 65,536 elements into a stated order costs 63,601 transfers one at a time and 4,096 by sorting them into place. In the model every other field on this site uses, the first is the cheap method and beats the second by a factor of eight. The two models disagree about which problem is easy, and they disagree by about the same factor in opposite directions.
The floor under a summary
An exact one-pass distinct-counter over a universe of u keys needs at least log2 of u-choose-u-over-2 bits of state — the same counting argument as the sorting floor, applied to memory states instead of outcomes. At u = 12 that is 9.85 bits, and an eight-bit candidate is shown to collide by running all 924 subsets.
An estimate borrowed from an easier problem
On a grid where every step costs one, the straight-line distance to the goal cuts a search from 543 cells to 325. On terrain where steps cost between one and nine it cuts 1,572 to 1,550, because it still believes every step costs one. Four exact distance tables, computed once, cut the same search to 252 — and cost 6,328 reads to build, so they pay for themselves on the fifth query.
The floor under a window
An exact count of the ones in the last W arrivals needs W bits, and the argument is a pigeonhole that can be performed rather than quoted — 1,024 windows, an eight-bit state, the colliding pair produced, and the two answers it cannot tell apart.
A floor that holds if something else does
The four lower bounds on this site are proofs. This one is a chain of implications with a conjecture at the top, and neither end of it is proved. The link that can be performed is performed here — checked over 55,754 formulas, 918 of them unsatisfiable — and the link that cannot is quoted and marked as quoted.
A table wider than its input
The knapsack table has (n+1)(W+1) cells and is called polynomial. Adding one character to the input doubles it — across four settings the table grows sixty-four times while the input it is written from grows by half.
The pass that runs the other way
Exact heavy hitters over the last 4,096 of 40,000 arrivals cost 40,000 reads and a ring of 4,096 keys and stamps read forwards, and 4,096 reads with no stamps read backwards. Every lower bound in the sliding-window model is a bound about an access pattern, and the word doing the work never appears in the statement.
A floor one pass cannot get under
An exact one-pass selector must reach a different memory state for every prefix it might have read, and the pigeonhole that proves it is small enough to perform — nine hundred and twenty-four prefixes through a nine-bit state, the collision produced, the suffix that separates it, and two true medians it cannot both return. Ten bits collide on none, so the bound is exact — and a second pass walks under it by a factor of ninety.
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 bound the search finds for itself
A spelling checker that computes the full edit-distance table against every word in a 2,424-word vocabulary fills 156,714 cells for each misspelt query. Bound each table by the best distance found so far, and abandon it the moment a whole row exceeds that bound, and the same search fills 40,273 and finds the same words. Meet the candidates nearest in length first and it fills 26,203, starting a table for exactly the words a search that knew the answer in advance would start. The last factor of 1.7 is the price of not knowing, and it is largest when the misspelling is smallest.
The branch that cannot reach an answer
Seventy-two rank operations over the pattern remove 27,906 of the 39,957 interval extensions a bounded-error index walk performs — 70% of the tree, at a budget of three. The share grows with the budget, which is what a pruning has to do to be worth its cost.
The columns the candidates share
Three thousand tables against one query, and most of them begin the same way. Stored as a trie, the 2,424-word vocabulary has 7,710 distinct prefixes holding 17,239 letters, and a search that computes one column per prefix reads 61,449 cells against 156,714 — before it applies any bound at all. Apply the bound at a prefix instead of at a word and it reads 16,958, beating a list search that was told the answer in advance.
The errors the rest of the pattern needs
Read the pattern left to right in an index of the reversed text and count the points where the interval empties. That count is a lower bound on the errors any alignment of the prefix must contain, it costs 72 rank operations, and it removes 70% of a search tree.
The cost that is the size of the answer
Ten range-minimum queries answer the listing at every point of a sweep where the occurrences run from 30 to 790. They cost 256 to 288 node visits — and the scan they replace costs 30 to 790, so the output-sensitive method loses until about thirty occurrences per document.
Work that falls as the answer grows
Output-sensitive usually means the cost rises with the answer instead of with the input. A descent over a document array costs five operations per document at an answer of seven and two at an answer of thirty-two, because the paths to many leaves share their tops.
Proportional to the answer, not the alphabet
At a fixed alphabet of thirty-two, a loop costs three hundred and twenty ranks whether one symbol is present or all of them. The descent costs ten and sixty-two. The experiment has to move the answer without moving the alphabet, and the obvious sweep moves both.
The count of the part that was read
Handing back the smallest ten of 65,536 keys in order costs 965,656 comparisons by sorting them and 65,670 by a knockout tournament, against a floor of 65,526. Read to the last element, the same tournament makes exactly merge sort's 965,656 — it is merge sort, charged one element at a time. A sort's count has no term for how much of its answer anyone reads, and the two floors that do have one cannot simply be added.
Where a crossing moved to
The prediction was that a succinct range minimum would move the document listing's crossing "to a handful". It moves it from 32 occurrences per document to 11 — a factor of three, not an order of magnitude — because a constant-time query is ten lookups rather than one.
The sort that makes none of them
Every count on this collection is a count of comparisons, swaps, reads or writes, and radix sort makes zero of the first. On 65,536 keys it moves five times less data than merge sort, misses the cache three times more, and sits 954,037 comparisons under the floor no comparison sort can go beneath — which is not an achievement, because the floor was never a statement about it.
Every pair must be asked
Ask whether a six-vertex graph is connected, one pair of vertices at a time, and the best possible algorithm needs all fifteen questions on its worst graph. The claim that this holds for every monotone property of graphs is a conjecture fifty years old. At four vertices it can be settled completely: all 2,046 properties that do not depend on vertex names need every pair. Name one vertex, and the count drops from ten to four.
A bound that has to be paid for
The pruning removes seventy per cent of a search tree for seventy-two rank operations. It also needs an FM-index of the reversed text — 17,033 bits against the forward index's 17,032 — which doubles the structure whose small size was the entire argument for walking an index.
Two 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 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 questions a sort asks twice
Selection sort makes 32,640 comparisons on 256 elements and 19,561 of them have answers it already holds. Remove every one and it still makes 7.8 times the information floor, because a question can be new and nearly worthless: insertion sort repeats nothing at all and removes 0.72 of a bit per comparison where merge sort removes 0.96. And bubble sort, less its repeats, makes exactly insertion sort's comparisons — at every size.
A 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.
The 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.
A bit for every bit
A grid over 3,612 points is 43,344 bits of payload. The smallest any structure can be that distinguishes one permutation of 3,612 things from another is 37,485. There is 16% to play for, and the deferral that asked for a compressed grid assumed there was much more.
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.
A code word is at least one bit
A wavelet tree of plain vectors reaches the entropy by its shape, and a Huffman code word cannot be shorter than one bit. On a collection whose document array has an entropy of 1.69 the tree costs 1.98, and the gap is a floor rather than an inefficiency.
The exponential is in the expression
The subset construction on one family reaches two to the k plus one states, exactly and not approximately. A literal of the same length gives eleven. Both are regular expressions and the difference is that one of them asks the machine to remember something.
Named alongside it
The objects these essays reach for when they reach for this one.
MeasurementComparison countHonest limitTrade offCounting argumentOutput-sensitiveWorst caseExhaustive searchFalsificationInformation floorPruningAdversary argument