Lower Bounds and Adversaries

The question

A club keeps a ladder of twelve players with hidden strengths. Every game between two players reveals which one is stronger; draws never happen.

The club wants to know four things, and each has a price in games:

1. the champion (the strongest player);
2. the champion and the weakest player together;
3. the runner-up;
4. the full ranking.

This module is not about how to find these. That's easy. It is about the other half of every algorithmic claim: how many games must any schedule use, however clever? An answer to that is a lower bound. Together with an algorithm that meets it, a lower bound is how you know you are done.

Measuring algorithms is not a lower bound

The obvious approach is to try some algorithms and count. On B:

• Champion, then weakest. Find the maximum by a scan (11 games), then the minimum of the other eleven (10 games): 21 games.
• Merge sort ranks everyone in 32 games. Binary insertion (insert each player into the ranked list so far by binary search) does it in 29.

import math

B = [58, 91, 17, 44, 73, 30, 86, 12, 65, 39, 25, 50]

class Game:
    """A player whose comparisons are counted: each < is one game."""
    played = 0
    def __init__(self, strength):
        self.s = strength
    def __lt__(self, other):
        Game.played += 1
        return self.s < other.s

def merge_sort(a):
    if len(a) <= 1:
        return list(a)
    m = len(a) // 2
    x, y = merge_sort(a[:m]), merge_sort(a[m:])
    out, i, j = [], 0, 0
    while i < len(x) and j < len(y):
        if y[j] < x[i]:
            out.append(y[j]); j += 1
        else:
            out.append(x[i]); i += 1
    return out + x[i:] + y[j:]

def binary_insertion(a):
    out = []
    for p in a:
        lo, hi = 0, len(out)
        while lo < hi:
            mid = (lo + hi) // 2
            if p < out[mid]:
                hi = mid
            else:
                lo = mid + 1
        out.insert(lo, p)
    return out

def games(sort, values):
    Game.played = 0
    ranked = sort([Game(v) for v in values])
    assert [p.s for p in ranked] == sorted(values)
    return Game.played

assert games(merge_sort, B) == 32 and games(binary_insertion, B) == 29

Each count is an upper bound: the cost of one particular algorithm. It says nothing about the next algorithm someone invents. "Merge sort took 32, so ranking twelve players needs 32" is already false on this very ladder. A lower bound is a statement about every algorithm in a stated model, and proving one takes a different kind of argument. This module has two: counting the possible answers, and playing an adversary.

The model: only games count

In the comparison model the elements are opaque. The only question an algorithm may ask is "is $x<y$?", and its cost is the number of such questions. Arithmetic on strengths, hashing and looking at digits are all forbidden. Module 03 shows what changes when they are allowed.

A deterministic comparison algorithm, run on $n$ elements, is a decision tree. Each internal node is a question, each branch is an answer, and each leaf is an output. Its worst-case cost is the height of the tree. Here is one for ranking three players $a,b,c$ (left means "yes"):

Counting leaves: the sorting bound

Two different input orders must end at different leaves. If they reached the same leaf, the algorithm would give the same ranking for both, and one of them would be wrong. So a tree that ranks $n$ players has at least $n!$ leaves. A binary tree of height $h$ has at most $2^h$ leaves, so

$$h\ge {\log }_{2}n!.$$

And ${\log }_{2}n!$ is about $n{\log }_{2}n$. Since $e^n={\sum }_k{n}^k/k!\ge n^n/n!$, we get $n!\ge (n/e{)}^n$, and so ${\log }_{2}n!\ge n{\log }_{2}n-n{\log }_{2}e$.

def info_bound(n):
    """ceil(log2 n!) exactly, in integers: n! - 1 has that many bits."""
    return (math.factorial(n) - 1).bit_length()

assert math.factorial(12) == 479001600
assert info_bound(12) == 29 and info_bound(3) == 3 and info_bound(5) == 7
assert round(math.log2(math.factorial(12)), 2) == 28.84
assert round(12 * math.log2(12) - 12 * math.log2(math.e), 2) == 25.71

For the club: no schedule can promise the full ranking of twelve players in fewer than 29 games. Binary insertion used exactly 29 on B. (Its worst case over all orders of twelve is 33, so it is not optimal on every ladder. The true optimum for twelve is 30: the Ford–Johnson algorithm reaches it, and an exhaustive computer search by Wells in 1965 showed that nothing does better. The bound itself is still the right order of growth.)

# Ford–Johnson (merge insertion) ranks twelve players in at most 30 games.
assert sum(math.ceil(math.log2(3 * k / 4)) for k in range(1, 13)) == 30

The same argument holds on average. Over uniformly random orders, the average depth of the leaves is at least ${\log }_{2}n!$. The tool is Kraft's inequality, stated here and not proved: in any binary tree whose leaves have depths $d_1,\dots ,d_L$, ${\sum }_i{2}^{-d_i}\le 1$. Since $2^{-x}$ is convex, the average of the $2^{-d_i}$ is at least $2^{-\overline{d}}$, where $\overline{d}$ is the average depth. So $L·2^{-\overline{d}}\le 1$, which gives $\overline{d}\ge {\log }_{2}L\ge {\log }_{2}n!$. On all 120 orders of five players, the lower bound's average is ${\log }_{2}120=6.907$. Binary insertion averages $7.067$ and merge sort $7.167$.

Why counting leaves is not enough

The same count gives almost nothing for the champion. There are only $n$ possible answers, so the tree needs height only ${\log }_{2}n$. Yet everyone who has run a knockout knows the champion costs $n-1$ games. The count of possible answers is too crude here. What forces the extra games is that each game can eliminate only one player.

Theorem (minimum). Finding the weakest of $n$ players needs $n-1$ games, on every input. Draw a line between two players whenever they play. With fewer than $n-1$ games, these lines leave at least two separate groups. Take a group that does not contain the reported weakest player and lower every player in it by the same large amount. Results inside the group keep their order, and no other game result changes, because nobody in that group played anybody outside it, but the answer is now wrong.

The adversary

For harder questions, the proofs take the form of a game against an adversary. The algorithm asks "is $x<y$?". The adversary answers however it likes, subject to one rule: every answer must be consistent with some real ladder. An algorithm that is correct on every ladder must still be correct after this conversation. So if the adversary can drag the conversation out to $k$ questions before the answer is forced, then every algorithm needs $k$ questions on some input.

Take the champion and the weakest together, the club's second question. The adversary labels every player:

• N: has never played;
• W: has played and only won;
• L: has played and only lost;
• B: has both won and lost.

An algorithm can stop only when exactly one player has never lost (the champion) and exactly one has never won (the weakest). Every other player must have both won and lost. Track the potential

$$\Phi =2\#N+\#W+\#L,$$

which counts how much "not yet ruled out" is left. It starts at $2n$ and must fall to 2 before anyone can stop.

The adversary answers so that $\Phi$ falls as slowly as possible:

• N meets N: someone must win. $\Phi$ drops by 2, and this is the only kind of game that drops it by 2.
• N meets anyone else: the N player loses to a W and beats an L, so only one label changes. $\Phi$ drops by at most 1.
• W meets W: one of them becomes B, so $\Phi$ drops by 1. The same holds for L meets L.
• W meets L: the W player wins again. Nothing changes.
• Any game involving a B player: answer by the current strengths, raising a W opponent or lowering an L one first (a W still wins, an L still loses). No label changes, so $\Phi$ stays put.

Consistency is the step not to skip. An adversary that simply answered "yes, the first is weaker" to every question could be driven into $x_0<x_1$, $x_1<x_2$, $x_2<x_0$. That is a cycle no ladder can produce, and a "proof" built on it proves nothing. The fix is to keep a concrete strength for every player who has played. When a W player must win again, raise its strength above everyone seen so far. When an L player must lose again, lower it below everyone. A W player has never lost, so raising it cannot contradict any earlier result, and symmetrically for L. Some ladder always fits every answer given so far.

Now count. There are at most $\lfloor n/2\rfloor$ games between two N players, since each uses up two of them. Those games lower $\Phi$ by at most $2\lfloor n/2\rfloor$, and every other game by at most 1. Say $a\le \lfloor n/2\rfloor$ games are between two N players. They lower $\Phi$ by $2a$, so the other $2n-2-2a$ units of the fall each need a game of their own: $\text{games}\ge a+(2n-2-2a)=2n-2-a$. That is smallest when $a$ is largest, so

$$\text{games}\ge 2n-2-\lfloor n/2\rfloor =\lceil \frac{3n}{2}\rceil -2.$$

For twelve players that is 16 games, not the 21 of "champion, then weakest". Here is where that plan loses, drawn with six players against the adversary:

The bound is tight. An algorithm that first plays the players in pairs, which is $\lfloor n/2\rfloor$ games between two N players, can finish in exactly $\lceil 3n/2\rceil -2$ games. The point is to spend every N-versus-N game first, then to send each pair's winner and loser to where they can still matter. Writing that algorithm, and the adversary, is the lab's job.

The runner-up

The club's third question costs less than you might expect. Run a knockout: pair players up, winners advance, and an odd player out gets a bye. That finds the champion in $n-1$ games, the minimum possible. The runner-up lost only to the champion, so it is one of the players the champion beat. There are only about ${\log }_{2}n$ of those, one per round, so a second knockout among them costs at most $\lceil {\log }_{2}n\rceil -1$ more games.

The finalist, 65, is not the runner-up. 86 lost to the champion a round earlier. The runner-up is the best of all the champion's victims, not the last one.

Theorem (second largest, Kislitsyn). The knockout's $n+\lceil {\log }_{2}n\rceil -2$ games is optimal. Sketch: every player except the champion and the runner-up must lose to someone other than the champion, or else it could still be the runner-up. The adversary gives every player a weight, starting at 1. When two players who have never lost meet, the heavier one wins and takes the loser's weight into its own. Every other game is answered by any ladder that fits the results so far (one of the two has already lost, so nothing the adversary has promised is at stake). The champion's weight is $n$ at the end and at most doubles in each game it wins, so it must beat at least $\lceil {\log }_{2}n\rceil$ different players directly. Each game makes one loss. Everyone but the champion loses at least once, which is $n-1$ losses, and all of the champion's victims but one must lose a second time, to someone else: at least $\lceil {\log }_{2}n\rceil -1$ more. Why these answers always fit some ladder is skipped here.

For twelve players: 14 games. The easy alternative, two scans (champion, then champion of the rest), costs $2n-3=21$.

And the median?

Module 01 found the median in $O(n)$ comparisons, and the leaf count, ${\log }_{2}n$, is useless here too. A similar adversary proves that the median of $2m+1$ players needs at least $3m$ games. It sorts players into "surely below" and "surely above" and forces extra games among them. For fifteen players that is 21. Stronger adversaries push the bound past $2n$, and the best algorithms known use just under $3n$. The exact constant is open.

Measure the claim

A bound that holds for every algorithm is a statement you can test against any algorithm. Comparisons of merge sort and binary insertion on one seeded random order per $n$, divided by ${\log }_{2}n!$:

Each entry is one order, not an average. The theorem bounds the average over all $n!$ orders, so a single lucky order could in principle land below 1. At these sizes it doesn't: from one random order to the next the ratio moves by about a percent, so single orders sit close to their average, which the theorem keeps at or above 1. Both sorts land within a couple of percent of the bound. Neither is wasting much.

```python import random

def ratio(sort, n, seed): order = list(range(n)) random.Random(seed).shuffle(order) Game.played = 0 sort([Game(v) for v in order]) return Game.played / (math.lgamma(n + 1) / math.log(2))

for sort in (merge_sort, binary_insertion): rs = [ratio(sort, 1000, seed) for seed in range(20)] assert min(rs) > 1 and max(rs) - min(rs) < 0.01 ``` For the champion and the weakest together, against the adversary, the pairing plan uses 13, 148 and 1498 games for $n=10,100,1000$. That is exactly $\lceil 3n/2\rceil -2$. "Champion, then weakest" uses $2n-3$: 17, 197 and 1997.

A problem that looks different

A chip designer wants a circuit of fixed compare-and-swap units that sorts any four numbers. Each unit compares two wires and swaps them if they're out of order, and the same units are used whatever the input. How few units could possibly work? Nothing in the question mentions a club, yet one idea from this lesson gives a number straight away. The lab's last problem is a different one.

Practise

In the lab you:

• build the adversary yourself, and watch its labels and its potential move after every game it answers;
• trace a knockout on a new ladder, where the finalist is again a trap;
• write the pairing algorithm, then check it meets the $\lceil 3n/2\rceil -2$ bound exactly and that an adversary can't catch it out;
• measure two sorts against ${\log }_{2}n!$;
• solve one problem that doesn't say what it is, and prove that nobody can solve it with fewer games.

Recap

• You can now: say what a lower bound quantifies over; prove the ${\log }_{2}n!$ sorting bound with a decision tree; run a consistent adversary with a potential to force $\lceil 3n/2\rceil -2$ comparisons; and find the runner-up in $n+\lceil {\log }_{2}n\rceil -2$ games, knowing why that is optimal.
• Invariant: the adversary stays consistent with some input, and $\Phi =2\#N+\#W+\#L$ drops by 2 only when two never-compared elements meet.
• Complexity achieved: the minimum and maximum in $\lceil 3n/2\rceil -2$ (against $2n-3$), the runner-up in $n+\lceil {\log }_{2}n\rceil -2$ (against $2n-3$), and sorting within a few percent of ${\log }_{2}n!$. The first two are exactly optimal in the comparison model; the sorts are asymptotically optimal, $(1+o(1)){\log }_{2}n!$, but not exactly: the best schedule for twelve players needs 30 games, one more than $\lceil {\log }_{2}12!\rceil$.
• Failure mode: a lower-bound "proof" that only shows one algorithm is slow, or an adversary whose answers no input could produce.
• In real software: C++ std::minmax_element is specified to make at most $max(\lfloor 3(N-1)/2\rfloor ,0)$ comparisons, which is exactly the pairing bound. CPython's list.sort compares items only with <, so the sorting bound applies to it.
• Next: module 03 leaves the comparison model and sorts integers in linear time. The bound above is only as strong as the model it is proved in.

Check yourself

1. Why does the pairing plan need only $\lceil 3n/2\rceil -2$ games, and why can no plan use fewer?
2. Suppose a game could end in a draw, so the question has three answers: $<$, $=$ or $>$. Does the sorting lower bound change for distinct strengths?
3. On 1000 players, against the adversary, compare "champion, then weakest" with pairing. Where exactly does the first plan waste games?

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.