A Randomized Algorithm for Finding Maximum with O((log n)^2)
Polynomial Tests
Authors: Hing F. Ting and Andrew C. Yao
ABSTRACT
A well-known result by Rabin [1] implies that n-1
polynomial tests are necessary and sufficient in the worst case
to find the maximum of $n$ distinct real numbers. In this
note we show that, for any fixed constant c>0, there is a
randomized algorithm with error probability O(n^{-c}) for
finding the maximum of n distinct real numbers using only O((log n)^2)
polynomial tests.
DIMACS Home Page