93-01 A Randomized Algorithm for Finding Maximum with O((log n)^2) Polynomial Tests

DIMACS TR: 93-01

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.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-01.ps

DIMACS Home Page