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.