Adversary Arguments

Symptom

You need the largest and second-largest element of an array. The obvious way is two passes: $n-1$ comparisons for the max, then $n-2$ for the max of the rest. That is $2n - 3$.

Somebody points out you can do better, and shows you a tournament: pair up the elements, play off the winners, and the second-best must have lost directly to the best — so you only need to re-examine the $\lceil \log_2 n\rceil - 1$ elements the champion beat. That is $n + \lceil \log_2 n \rceil - 2$.

Now the real question, and the one that is actually hard: is that optimal, or is there a cleverer scheme still? You cannot answer it by trying algorithms. You need an argument that rules out all of them at once, including the ones nobody has invented.

The decision-tree bound (T003) will not do it here: it gives $\log_2$ of the number of outcomes, which for “find the top two” is far too weak. You need a different tool.

Statement

The technique, stated as a game:

An adversary answers the algorithm’s queries. It does not fix the input in advance. Instead it answers adaptively, keeping its answers consistent with at least one valid input, and choosing each answer to maximize the work still remaining. If the adversary can always keep two different answers alive after $k$ queries, no algorithm can be correct in $k$ queries.

The concrete result this post proves:

Since the tournament achieves this, the bound is tight, and the question is closed. Nobody will ever do better, and that is knowable in a page.

Argument

Two separate accounting arguments, one for each term.

Part 1: at least $n - 1$ comparisons. Every element except the maximum must lose at least one comparison — otherwise, for any element that never lost, the adversary is free to declare it the maximum, and the algorithm’s answer is wrong on some consistent input. Each comparison produces exactly one loser. So at least $n-1$ comparisons are needed just to identify the max.

Part 2: at least $\lceil \log_2 n \rceil - 1$ more. The second-largest element is exactly the largest of those that lost directly to the maximum. So the algorithm must, in effect, determine the max’s set of direct victims and find the best among them. If the eventual champion beat $k$ elements directly, finding the best of those $k$ costs at least $k - 1$ further comparisons by the argument above.

So the adversary’s job is to force $k \ge \lceil \log_2 n \rceil$: make the champion win many fights.

The adversary strategy — weights. Give every element a weight, initially $w_i = 1$. Interpret $w_i$ as “the number of elements this one could still be the best of.” When the algorithm compares $x$ and $y$, the adversary answers:

• If $w_x > w_y$: declare $x$ wins. Set $w_x \leftarrow w_x + w_y$, $w_y \leftarrow 0$.
• If $w_x = w_y$: declare $x$ wins (break ties arbitrarily). Same update.

The key property: a winner’s weight at most doubles per comparison. When $w_x > w_y$, the new weight $w_x + w_y < 2w_x$. When $w_x = w_y$, it is exactly $2w_x$. So after the champion has won $k$ fights, its weight is at most $2^k$.

At the end, the champion must have absorbed everything — its weight must be $n$, since every other element has been shown to be worse than something, and all that “worse-ness” ultimately routes to the max. So

$$2^k \ge n \quad\Longrightarrow\quad k \ge \lceil \log_2 n\rceil$$

The champion won at least $\lceil \log_2 n \rceil$ comparisons. Finding the best of its direct victims costs $\ge \lceil \log_2 n \rceil - 1$ more.

Total: $(n-1) + (\lceil \log_2 n\rceil - 1) = n + \lceil \log_2 n\rceil - 2$. $\blacksquare$

Why the adversary is allowed to do this. The move that feels like cheating is that the adversary has not decided the input yet. It is not cheating, and the reason is worth internalizing: at every point the adversary’s answers are consistent with at least one real input. If the algorithm stops early and announces an answer, the adversary exhibits a consistent input on which that answer is wrong. Since the algorithm must be correct on all inputs, it must be correct on that one. The adversary is a bookkeeping device for the sentence “there is always a bad input remaining,” and it lets you construct that input lazily rather than guessing it up front.

A second example, in two lines, because the technique generalizes. Searching an unsorted array of $n$ elements needs $n$ probes in the worst case: whenever the algorithm probes a cell, the adversary answers “not your target.” After $n-1$ probes, one cell is unexamined, and the adversary is free to put the target there or not. The algorithm cannot know. Same shape: keep two worlds alive.

Forbids

Finding max and second-max in fewer than $n + \lceil\log_2 n\rceil - 2$ comparisons. For $n = 1024$: at least $1032$. No algorithm, ever.

Finding the maximum in fewer than $n-1$ comparisons, by Part 1 alone.

Unsorted search in fewer than $n$ probes.

A “smarter” tournament. Since the tournament meets the bound, the entire space of possible improvements is empty. This is the practical payoff of a lower bound: it tells you when to stop optimizing, which is information you cannot get from benchmarking.

Does not forbid

It does not forbid doing better on real data, and this is where lower bounds get misapplied in engineering discussions. “Search is $\Omega(n)$, so don’t bother optimizing lookups” ignores that the bound is worst-case over unstructured input. Index the data and you are no longer in the model: a hash index is $O(1)$, a B-tree is $O(\log n)$, a Bloom filter answers most negatives in constant time. The adversary’s power comes entirely from the algorithm having no prior information, and every database ever built is an argument for buying some in advance.

It does not forbid randomized algorithms from beating the deterministic bound. A deterministic adversary knows exactly what the algorithm will do next, which is the source of its power. Against a randomized algorithm it cannot, because the next query is not determined. This is a real gap and not a technicality: randomized algorithms genuinely beat deterministic lower bounds for game-tree evaluation, and the correct tool for randomized lower bounds is Yao’s minimax principle, which fixes a hard input distribution rather than an adaptive adversary.

It does not mean the constant is achievable for related problems. The bound is tight here and famously is not for median selection: the best known algorithm needs about $2.95n$ comparisons, the best known lower bound is about $(2 + \epsilon)n$, and the gap has stood for decades. Adversary arguments give you real numbers; they do not promise to close.

It does not apply once comparisons are not the only operation. Same exemption as T003, and the same reason. If you can read the bits of the keys, the model is gone. The adversary’s weights presuppose that the only information ever extracted is “which of these two is bigger.”

It does not say the algorithm is bad if it uses more comparisons. The tournament is optimal in comparisons and has worse cache behaviour than the naive two-pass scan, which is sequential and predictable. On real hardware, for moderate $n$, the “suboptimal” algorithm frequently wins. A comparison-count lower bound is a statement about a cost model, and the cost model is not your machine.

Boundary

• Yao’s minimax principle. The right tool when the algorithm may randomize: the expected cost of the best randomized algorithm on its worst input equals the cost of the best deterministic algorithm on the worst input distribution. This converts a randomized lower bound into a deterministic one, at the price of having to invent a hard distribution.
• Information-theoretic bounds. The decision-tree argument (T003) is the other main technique, and the two have different reach. Counting leaves is easy and gives $\log_2(\text{outcomes})$; for max-and-second-max that yields roughly $\log_2(n(n-1)) \approx 2\log_2 n$, hopelessly weak. Adversary arguments track state rather than counting outcomes, which is why they get the linear term the counting argument misses. Reach for the adversary when the answer space is small but the work is large.
• Potential functions. The weight scheme above is a potential-function argument: define a quantity, bound how much one operation can change it, bound its start and end values, divide. That is the same machinery as amortized analysis (T006), used to prove a lower bound instead of an upper one.
• Where adversaries fail. They are only as strong as the invariant you can maintain, and inventing the right potential is genuinely hard — which is exactly why the median constant is still open. There is no procedure for finding the weight function; the technique tells you what to look for, not how to find it.
• Adversaries in complexity theory. The same idea, scaled up: relativization results (Baker–Gill–Solovay) build an oracle adversary that answers queries to keep two worlds alive, one where $P = NP$ and one where it does not. That is this argument, at the level of entire complexity classes, and it is why diagonalization alone cannot settle the question.

Read next