A lower bound cannot be measured, because a measurement is about one algorithm and a bound is about all of them. It is proved instead by an adversary who holds no array and answers each comparison so as to keep the largest number of outcomes possible. That argument gives n − 1 comparisons for the maximum, ⌈3n/2⌉ − 2 for the minimum and maximum together, and n + ⌈log₂ n⌉ − 2 for the second largest, and each of the three is met exactly.
Core ideas
The hard idea is the quantifier. Everything else on this course measured one algorithm; this proves something about all of them at once.
Running an algorithm tells you what that algorithm did on that input. A lower bound says no algorithm can do better on its worst input, which quantifies over a set no lab can enumerate. The adversary supplies the quantifier: because it answers whatever it is asked, its argument covers every strategy, including ones nobody has written.
It never commits to an array. It keeps a set of arrays consistent with every answer it has given, and each new answer is chosen to leave the larger set. For the maximum, it answers so that exactly one element is eliminated per comparison: any algorithm stopping before n − 1 comparisons has left two elements unbeaten, and the adversary can still name an array making either of them the maximum, so the answer was not determined.
The adversary gives a floor; an algorithm gives a ceiling; when they coincide the question is closed. All three bounds here are met. Pairing the elements before scanning finds both ends of eight keys in exactly 10 comparisons, and the tournament finds the second largest of eight in exactly 9 — and the lab verifies the second of those on every one of the 40 320 arrangements.
The material
How an adversary argument works, the three bounds it gives here, and the algorithms that meet them.
An adversary argument proves a lower bound on the number of comparisons any algorithm needs. The adversary answers each comparison the algorithm makes, without fixing the input in advance, subject only to consistency: there must always remain at least one input agreeing with every answer given. If, after fewer than B comparisons, two different answers are still consistent with everything said, the algorithm cannot have determined the result, so B is a lower bound.
Any comparison-based algorithm that reports the maximum of n elements makes at least n − 1 comparisons in the worst case.
Call an element unbeaten if it has not yet lost a comparison. Initially all n are unbeaten. The algorithm can only report a maximum when exactly one element is unbeaten: if two were, the adversary could consistently make either of them the largest, so the reported answer would not be determined.
The adversary answers every comparison between two unbeaten elements arbitrarily but consistently, and every other comparison in whatever way keeps its options open. Each comparison eliminates at most one element from the unbeaten set, since only the loser leaves it.
Going from n unbeaten elements to one therefore takes at least n − 1 comparisons. A single scan makes exactly that many, so the bound is tight.
□
Finding the minimum and the maximum of n elements requires at least ⌈3n/2⌉ − 2 comparisons in the worst case, and an algorithm achieves it.
The algorithm is the more instructive half. Pair the elements and compare within each pair, which costs ⌊n/2⌋ comparisons and settles, for each pair, which member can still be the minimum and which can still be the maximum. Then find the minimum among the ⌈n/2⌉ losers and the maximum among the winners, at ⌈n/2⌉ − 1 comparisons each. A pair therefore costs three comparisons for two ends rather than four, and at n = 8 the total is 4 + 3 + 3 = 10 against the 14 of two independent scans.
Any algorithm reporting the second largest of n elements makes at least n + ⌈log₂ n⌉ − 2 comparisons in the worst case, and the tournament meets it.
The second largest must have lost to the maximum, because it lost to nobody else. So the algorithm has to find the maximum first, at n − 1 comparisons, and then find the largest among those the maximum beat. A knockout tournament beats the fewest possible: the winner plays ⌈log₂ n⌉ rounds, so only ⌈log₂ n⌉ elements ever lost to it, and picking the best of those costs ⌈log₂ n⌉ − 1 more. At n = 8 that is 7 + 3 − 1 = 9, which is the lab's measured count, and it never exceeds it on any of the 40 320 arrangements the sweep runs.
The misconception the tournament breaks is the natural one: scan the array keeping the best two, which compares each new element with the second best and sometimes with the best as well, and costs up to 2n − 3 — 13 at n = 8, measured at 11 on the lab's array. The tournament's saving is structural rather than clever: it remembers who lost to the winner, so the candidate set is ⌈log₂ n⌉ instead of n − 1.
One row of the lab's table is different in kind from every other figure on this course. At sizes up to eight it runs the tournament on every arrangement of 1 … n — 40 320 of them at n = 8 — and reports the worst count found, whether any exceeded the bound, and whether any returned the wrong element. None exceeded and none was wrong, and the worst equals the bound. That is a claim about every input of that size, which is as close to a quantifier as a measurement gets, and it is still not a claim about every algorithm.
Discrete Mathematics' “Searching and Sorting” proves that sorting n elements by comparisons needs at least ⌈log₂ n!⌉ of them, by counting the leaves a decision tree must have. That is the same kind of statement as the three above and it is used here as a thing to reduce to rather than reproved: every panel on this course prints it beside a measured count, and Geometric Algorithms will later reduce sorting to convex hull in order to inherit it.
Interactive
Answer comparisons to keep the most outcomes alive, then meet each bound with an algorithm
Method
Take the adversary's side. The question is never what your algorithm does, but what it has not yet ruled out.
For the maximum it is the number of elements that have not yet lost. For the second largest it is the number of elements that could still be second. The bound comes from how fast a single comparison can move that quantity, which for the maximum is by one.
The rule must never contradict an earlier answer: there has to remain at least one array agreeing with everything said. An adversary that cheats proves nothing, and the lab's is consistent by construction — at any point it can name an array matching every answer it gave.
It can only stop when one candidate is left. Divide the distance by the most one comparison can cover, and that is the bound. Play the lab's game and watch the counter rise to n − 1 however cleverly you choose your pairs.
A bound with no matching algorithm is a floor of unknown height. Pair-then-scan meets ⌈3n/2⌉ − 2; the tournament meets n + ⌈log₂ n⌉ − 2. Run each and check the measured count against the bound on the panel.
The count you ran up is a measurement of one game. The bound is a proof about every algorithm. The sweep over all arrangements is neither: it is a complete statement about one algorithm at one size, and the lab labels it as the one figure on the page that is not about a single input.
The array is the lab's seeded shuffle, 2 5 4 3 7 8 6 1. The strategy is to pair first, so that one comparison per pair decides which member can still be the minimum and which can still be the maximum.
The saving is entirely in step one. Without it, every element is a candidate for both ends and each has to be tested against both running extremes. With it, one comparison per pair halves both candidate sets at once, so two elements cost three comparisons rather than four — 3n/2 rather than 2n, and the − 2 is the two extremes that need no final comparison.
Now switch the lab to the second-largest game at the same size. The tournament costs 9, the bound is 8 + 3 − 2 = 9, and keeping the best two in one scan costs 11 against a worst case of 2n − 3 = 13. Only three elements ever lost to the winner, which is ⌈log₂ 8⌉, and that is the whole reason the second largest is nearly free once the largest is known.
For a faded rehearsal, play the maximum game at n = 8 and try to finish in six comparisons. The supplied first move is the invariant to watch: the panel's unbeaten count starts at 8 and falls by at most one per comparison. Say, before you start, how many comparisons you will need, then verify that no ordering of your questions changes it.
You should be able to give the unbeaten-set argument for n − 1, describe the pairing strategy and count it to ⌈3n/2⌉ − 2, explain why only the winner's losers can be second, and distinguish a sweep over all inputs from a claim about all algorithms.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.