Adversary argument
= Adversary argument
A method for proving that an <algorithm> must perform a certain amount of work: supply observations compatible with more than one possible input until enough information has been acquired to distinguish the required outputs. For exact membership in an arbitrary <array>, answering every inspected location with a value other than the target forces inspection of every location in the absent case, since any uninspected location could contain the target.