Lower bound — where it appears
Named by 52 essays across 11 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 written before it 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.
A trie fitted to its queries
A nearest-word search over a trie of 2,424 words gives a column to about 30% of the prefixes each query, and it was proposed that a stream of queries would pick out a part of the trie worth keeping and a part worth collapsing. A hundred queries have visited 93% of it; two thousand, 99.5%. A stream does not choose a part of the trie. It chooses a distance: misspelt vocabulary words all lie within two edits, and a search that starts at the median past answer does a fifth of the work of one that discovers its bound. Misspellings of words the vocabulary lacks break that, unless the search tries the learned bound once and then gives it up.
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.
A second try before any feature
A nearest-word search that learned one starting bound for a whole stream was proposed a bound for each query instead, read off features the search can compute before it walks. The proposed feature separates nothing: 58% of misspelt vocabulary words and 53% of words the vocabulary lacks begin with a real three-letter prefix. Length and unseen letter-triples do predict distance, and still buy about 1%, because the best start is two for almost every class. What closes half the gap to an oracle is a second cheap walk: one, then two, then discover.
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 merge that can say equal
When two sorted lists draw their keys from a few values, equal keys can go on either side of each other, so far fewer answers are needed and the counting floor falls. Merging four keys into four over four values needs only 27 answers, not 70, and the floor falls from seven comparisons to five. A merge whose comparisons answer only 'at most' still needs seven on its worst input, exactly as many as distinct keys, because it can never learn that two keys are equal. A merge whose comparisons can answer 'equal' needs five and meets the floor. Solved exactly over every input, the third answer is the whole difference, and on average it is worth more than an optimal strategy.
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.
A floor under a product
Every lower bound written here so far puts a floor under one quantity. The published time–space bound for sorting puts one under a product: T·S is Ω(n²), so buying time with space and space with time cannot both be done. Measured, heapsort's product is 0.0028 n² — four hundred times under a bound nothing can beat. The bound is not wrong. It is stated in a model where the input may not be written, and every sort here writes to the input, which is where its working memory actually is.
A product paid for in blocks
The published floor under sorting puts a bound on time times space, and a read-only family that scans its input over and over meets it, while every in-place sort sits far above it. Counted in block transfers rather than reads, the floor itself moves to n²/B: the family meets it at every block size, and so does every sort once memory holds the whole array. With a memory of 512 cells, quicksort sits a fixed eight times above the family at every block size, because partitioning is itself a scan. Only heapsort's distance grows with the block, from ten times at a line of one to 285 times at 64. The prediction that the family's lead would widen towards B holds against heapsort and nothing else.
A count that names every point
A grid that can report the points in a rectangle can be no smaller than log₂(z!) bits, because reporting them recovers the permutation. A grid that only counts them was left open as possibly smaller. Exactly, it cannot be: counts alone decode every point, and on the phrase index's 3,612 points 42,860 count questions recover the whole permutation, so an exact counter pays the same floor of 37,485 bits. Approximately it can — and the rectangles a phrase index asks are where an approximate count is worst. They hold 2.6 points on average and a third of them hold exactly one; the wavelet grid cut to eight of its twelve levels, 8% under the floor, counts 46% of them right.
The moves no stable sort can skip
Any sort must move every key that starts out of place, and with one spare cell it must spend one more move on each cycle of the permutation. Against that floor, a stable merge sort trimmed to the keys not already in place moves 1.46 times the least possible on records written in overlapping batches — the two thirds the prediction named, and for its reason. On a sorted file with a late tenth appended it was predicted within twice the floor and moves 15 times it, because the late tenth arrives in random order and sorting it among itself is two thirds of the work.
A test that is the top of the search
A phrase index asked whether a pattern occurs only needs to know, split by split, whether a rectangle of its grid holds a point. Stopping the grid's descent at six of its twelve levels was predicted to turn away nine in ten of the splits that come to nothing, for half the grid's bits. It turns away three in four, and the ones it lets through sit a median of five rows from a point. The test is never wrong, but the existence query had little left for it to save: patterns that occur are settled by their first split 94% of the time, and most patterns that do not occur never reach the grid.
The memory a product does not charge
Time times space charges a sort for the cells it writes and not for the fast memory it needs to write them cheaply. Counted three ways, on random keys in lines of eight, a read-only family stays within a factor of eight of the floor with 32 to 256 cells of fast memory at every length, while heapsort needs all of n and quicksort an eighth of it. Quicksort's need falls far faster than predicted as the factor loosens. And the product the floor leaves out, transfers times fast memory, separates the two kinds of sort completely: no read-only sort can push it far below n²/B, and quicksort reaches a twentieth of it.
The lines a sort writes back
A replay that charges a transfer for every line brought into fast memory and none for a line sent back flatters every sort that writes in place. Charged for its write-backs, quicksort's transfers rise by 1.9 at every memory short of n, as predicted, and heapsort's by 1.8, not the predicted three, because no line can go back more often than it came in. The cost that changes the account is the last one: at n itself every in-place sort pays two reads of its array, so none of them can come within a factor of two of the floor, while the read-only family reaches 1.07.
A buffer that does not shift its tail
The read-only family of sorts scans its input once for each batch of the smallest values not yet output, keeping them in a buffer; charged for the dirty lines it sends back to slow memory, its least transfers × fast memory rose from 1.29 of n²/B to 1.87, because a sorted buffer takes each value by shifting every larger entry one place. Kept as a max-heap instead, the buffer was predicted to write back about a third of the lines it reads below its own size and to bring the product back towards 1.29. At a buffer of 64 cells it writes back 33% at its best memory, against 45%, and its least product falls to 1.71: right about the share, wrong about the product, since a third written back is still a third more transfers. At 256 cells the heap does more than predicted — 1.47 million accesses against 6.94 million, a third of the misses — and its least product, 1.62, is under any buffer's on the earlier charge. At 16 cells it does nothing.
Named alongside it
The objects these essays reach for when they reach for this one.
Trade offHonest limitMeasurementComparison countWorst caseCost modelOutput-sensitiveCounting argumentExhaustive searchPruningIndex sizeInformation floor