Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Decision tree — where it appears

A tree whose internal nodes are comparisons and whose leaves are outcomes, from which a floor follows by counting the leaves needed. Counting its leaves gives a floor that binds every comparison-based method, and the counting can be performed exhaustively at a size a figure can draw.

Named by 4 essays across one field — each of them below, with the objects they name alongside it.

every algorithm that makes at most 4 comparisonsthe 24 orderings of 4 elementsroot16 leaves16 seated · 8 with no leafone comparison per level, two outcomes per comparison⌈log₂(4!)⌉ = 5 comparisons

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.

floors · Floor with the edge — connected01234567all 8 edges presentwithout it — two components01234567one edge withheld, everything else identicalV = 8, E = 8Ω(E), by adversary rather than by counting

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.

floors · Floor probe 1: 0–1 absent9 still to ask10 of 10 as good as anyprobe 2: 0–2 absent8 still to ask9 of 9 as good as anyprobe 3: 0–3 absent7 still to ask8 of 8 as good as anyprobe 4: 0–4 present6 still to ask7 of 7 as good as anyprobe 5: 1–2 absent5 still to ask6 of 6 as good as anyprobe 6: 1–3 absent4 still to ask5 of 5 as good as anyprobe 7: 1–4 present3 still to ask4 of 4 as good as anyprobe 8: 2–3 absent2 still to ask3 of 3 as good as anyprobe 9: 2–4 present1 still to ask2 of 2 as good as anyprobe 10: 3–4 absentdecided1 of 1 as good as any5 vertices · 10 pairs · 59,049 states solvedsolid: present · dotted: absent · coloured: this probe

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.

floors · Floor length of the longer list, nshorter, m1234561234561floor 12floor 22floor 23floor 33floor 33floor 33floor 34floor 45floor 45floor 56floor 55floor 56floor 67floor 67floor 77floor 78floor 79floor 89floor 810floor 911floor 10the optimum is one above the floorthe floor is reachedevery cell solved exactly · m ≤ n ≤ 6large: the optimum · small: ⌈log₂ C(m+n, m)⌉

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.

floors · Floor

Named alongside it

The objects these essays reach for when they reach for this one.

Lower boundAdversary argumentAdjacencyAverage caseConnectivityEvasivenessExhaustive searchHonest limitWorst caseAdjacency listBinary searchComparison count

All concepts