As a generic stand-in for the kind of problem it solves, suppose you have a function acting on {1, ..., N} which returns True on one and only one value in this set. If all you can do with this function is try it out on numbers, then it takes an average of (1/2)N steps to find the answer.