## 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