Abstract (Michael Ben-Or)
How many comparisons are needed to find the maximum, or the median,
of n real numbers, if we allow randomization, and the free computation
of any analytic real function of the inputs. Rabin (1972) proved that
n-1 comparisons are needed to verify that a given element is the
maximum if no error is allowed, and Ting and Yao (1994) gave a randomized
algorithm for finding the maximum with O(log^2 n) expected number of
comparisons if a small error probability is allowed. We present a new
simple proof of Rabin's result and extend this to show that for all k<n-1,
at least k comparisons are needed to verify that a given element is
the maximum if the error probability is less than 1/2^k. We further show
that Omega(n) comparisons are needed to verify that a given element is
the median of n real numbers if the error probability is O(1/n^(3/2)).
Last modified: August 30, 1995.
Kim Skak Larsen
(kslarsen@imada.sdu.dk)