A game against the algorithm
An adversary argument proves a lower bound: a statement that no algorithm can solve a problem using fewer than some number of operations. The technique imagines an adversary who answers the algorithm's queries on the fly, choosing answers that remain consistent with some input while forcing the algorithm to keep working.
How the game is played
The algorithm asks questions, such as comparing two elements. The adversary does not fix the input in advance; instead it answers each query in whatever way keeps the most possibilities open, as long as the answers stay consistent with at least one valid input. If the algorithm stops too early, the adversary can exhibit two different inputs consistent with all its answers that demand different outputs, proving the algorithm was wrong.
- The adversary maintains a set of inputs still consistent with its answers.
- Each query may only shrink that set, and the algorithm cannot stop while two answers remain.
What it establishes
This is a worst case lower bound that applies to every algorithm in the model, not just one. It is how we prove that finding the maximum of n elements needs at least n minus one comparisons, and it underlies the comparison sorting lower bound. Because the adversary is unbeatable by construction, the bound is unconditional.
Key idea
An adversary argument proves an unconditional lower bound by letting a malicious answerer respond to queries so as to keep multiple inputs consistent, forcing any correct algorithm to perform at least the claimed number of operations.