The floors
The floor under every comparison sort
The decision-tree argument for the comparison-sorting lower bound, why it is a statement about every algorithm rather than any one of them, how log₂(n!) is computed exactly without overflowing, and what the word "comparison" is doing in the theorem.
How close anything gets to the floor
Every sorting algorithm on this site measured against log₂(n!), why the ratio is more informative than the complexity class, and what an algorithm within 2% of an unbeatable bound says about how much room is left.
The floor moves when the question does
How the decision-tree argument gives different floors for sorting and searching, why binary search is optimal rather than merely good, and what happens to the bound when the algorithm is allowed to look at values instead of only comparing them.
The adversary who hides the edge
The adversary argument for connectivity, why the decision-tree method that settles sorting says nothing here, and what a lower bound proved by an opponent rather than by counting looks like.
The floor when the values repeat
What the information-theoretic bound on sorting becomes when keys are not distinct, why quicksort's comparison count triples on such inputs, and where counting sort's linear time comes from.
A floor on the bits
The information-theoretic floor on approximate membership, why it is a bound on space rather than on time, and what it means that a Bloom filter sits a constant factor above it at every accuracy.
A floor under a run count
The counting floor under any run-based representation, computed exhaustively for every text of twelve characters, and the exact slack in the encoding that stores runs.
The floor under moving data
The external-memory sorting lower bound, where it comes from, why it is a floor rather than an aspiration, and the measured gap between it and a real sort.
What a reordering costs to undo
Four permutations of the same 8,192 symbols — none, a shuffle agreed in advance, a full sort, and the Burrows–Wheeler transform — each followed by move-to-front and coded at its zeroth-order entropy, with the side information its inverse needs added. The sort's saving is exactly cancelled, and every string of eight characters over three letters is enumerated to check that it is.
The bits a coder emits
Shannon's bound as a measured quantity — what the entropy of a stream is a floor on, how close each coder gets, and why this floor moves when nothing about the data changes.
The floor under a summary
The site's third kind of lower bound, counting memory states rather than comparison outcomes, performed by exhaustion rather than quoted — and what changes when the answer is allowed to be approximate.
The floor under a window
The memory-state lower bound for exact sliding-window counting, performed exhaustively, and what is measured rather than proved about the approximate case.
A floor that holds if something else does
The conditional lower bound under edit distance — split-and-list from satisfiability to orthogonal vectors, verified by exhaustion, and the identity that makes a quadratic scan exactly exhaustive search.
The pass that runs the other way
What making the direction of a pass a parameter reveals about the sliding-window model, why the same trick is worth nothing on a question about the prefix, and where a backward pass is not available at all.
A floor one pass cannot get under
The sixth lower-bound argument here and the third of the memory-state kind — the construction, the exhaustive search that performs it, why it is tight, and what a second pass does to it.
The floor charged at every level
What a Space-Saving fold actually charges a surviving key, why the account is exact, and why a model counting only the shard floors was right at eight shards and half the answer at sixty-four.
A floor with two variables in it
Why a Space-Saving floor is linear in a shard's mass under one partition and not a power law at all under another, and what the second variable is.
Work that falls as the answer grows
What proportional-to-the-answer means when the constant is not constant, measured across a sweep where the range grows twenty-five-fold and the answer fivefold.
Proportional to the answer, not the alphabet
The cost of an interval enumeration against how many symbols the interval holds, at fixed sigma, and the logarithmic discount that makes the per-symbol cost fall.
From the right, two of sixteen
What a traversal order is worth, measured by reversing it, and the second silent shortfall of the same shape in two strands.
Every pair must be asked
The adjacency-matrix model solved exactly: every partial state of the probing game enumerated at up to six vertices (14,348,907 states), every property of four-vertex graphs checked, the parity argument that settles most of them in a line, the two controls that show what the conjecture's hypotheses are doing, and how far below the worst case the optimum sits on a random graph.
The floor a merge cannot reach
The information floor for merging, log₂ C(m + n, m), checked against the exact optimum found by solving the merge game over every state of knowledge up to seven keys a list: where the worst case misses the floor and by how much it grows, the adversary argument that forces 2m − 1 on equal lengths, how close the best average gets, and four real merges measured against both floors over every interleaving and at ratios up to a thousand to one.
The order inside a tie
Rotations sorted by their first k characters for k from zero to the full context, under two rules for the order inside a tie. Every string of eight characters over three letters is enumerated to count what each costs to undo, 8,192 symbols from three sources are coded after move-to-front, and the characters the sort reads are counted, to find where the sort and the transform sit in one family.
A result the size of its own noise
The four-character context sort against the full transform, measured over sixteen streams rather than one, on two sources that differ only in whether each word depends on the one before it. The advantage at every context length with its spread, the run breaks split by whether a context reaches a word boundary, the group sizes a tie rule has to work with, and the same null across six vocabulary sizes.
Where a context stops naming the letter before
The share of a text's positions whose context of k characters is preceded by more than one distinct character, computed in one pass for five sources — two synthetic word sources, words from a whole corpus vocabulary, and slices of two fixed corpora — against the sweep over k that measures the context sort's bits a symbol against the full Burrows–Wheeler transform: all ambiguity, ambiguity inside a word that continues, the sweep's own curve, where each crosses its threshold, and where the ambiguity lies at five characters.
The merge that can say equal
The game of merging two sorted lists over an alphabet of k values, solved exactly for lists of three, four and five keys by memoised minimax over every order type of the two lists, in two games — comparisons answering at-most-or-not, and comparisons answering less, equal or greater: the worst-case optimum against the counting floor, the number of answers needed against the number of inputs, the textbook merge and the optimum on average, one input drawn as value classes with each key's range of correct positions, and each game's distance from the floor.
The repeats a context cannot see past
The conditional entropy of the character before a context, given the next k characters, on five sources of eight 8,192-character streams — estimated in one pass three ways and split at word boundaries, then set against each stream's twin with its words shuffled — beside the share of positions inside a repeated string longer than the context: the three estimates on independent words, the word order's information on every source, the corpora written and shuffled, the share of long repeats, and each technical stream's repeats against what a context sort loses on it.
The deepening the sort was already doing
Sixteen streams of 8,192 characters, eight from a corpus of essays and eight from a corpus of technical writing, sorted as rotations by their first 2, 4 or 8 characters, by the same sort deepened inside ranges whose contexts repeat at twice the depth, and by the full Burrows–Wheeler transform, each coded by move-to-front and zeroth-order entropy and each charged the characters it reads: bits against characters read, the transform's comparisons by depth, the bits lost stream by stream, where the deepened sort's reading goes, and what stopping at k characters buys.
The order the column cannot see
Sixteen streams of 8,192 characters from a corpus of essays and a corpus of technical writing, sorted as rotations by their first four characters, with the ranges that sort leaves deepened to the transform's order under a budget of characters, taken longest agreement first or most different preceding characters first: bits above the transform against characters read, two ranges drawn with the character before each rotation, the transform's deep reading by depth and by how many characters precede it, and stream by stream the reading of a sort that skips the ranges preceded by one character.
The runs a short list cannot have
Two sorted lists whose keys take at most k values: the three-way merge game solved exactly at four keys a list with and without comparisons between two keys of one list; the three-way textbook merge against the same merge galloping over each run of equal keys, exactly over every input at four keys and sampled at 64 to 4,096 keys a list; comparisons a key against k at 1,024; the saving against the mean run length; the largest k at which galloping pays against list length; and the galloping merge's comparisons across and inside the lists.