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

Adversary argument — where it appears

A lower-bound proof in which an opponent answers the algorithm's questions instead of fixing the input in advance. Each answer is chosen to keep as many possible inputs alive as it can, so the bound holds for every algorithm at once rather than for a particular one.

Named by 5 essays across 2 fields — each of them below, with the objects they name alongside it.

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 1416642561k2k4k8k16k33k66k11010010³10⁴10⁵10⁶keys handed backcomparisons no method can go underthe losers, and the outputs' ownorderevery element not handed back losesthe answer is one of n!/(n−k)!sequences65,536 keyseach is a claim about every possible method

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.

counting · Count 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 11010010³10⁴10⁵10⁶k, the number handed backcomparisonstournament, measuredfloor that names the outputsbest earlier floorn = 65,536, one shuffled inputthe floors are worst-case, the count is one input

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.

counting · Count

Named alongside it

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

Lower boundExhaustive searchHonest limitWorst caseComparison countDecision treeInformation floorAdjacencyAverage caseConnectivityEvasivenessFalsification

All concepts