On selecting the largest element in spite of erroneous information

In this paper, we study the problem of finding the largest of a set of n distinct integers using comparison queries which receive “yes” or “no” answers, but some of which may be erroneous. If at most e queries can receive erroneous answers, we prove that (e+1)n−1 comparisons are necessary and sufficient to find the largest. If there is further restriction that errors are confined to “no” answers and that all “yes” answers are guaranteed to be correct, then 2n+2e−4 comparisons are sufficient. This contrasts with earlier results relating to errors in binary search procedures where both versions of the problem have the same complexity.