A randomized algorithm for finding maximum with O((log n)2) polynomial tests

A well-known result by Rabin 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 agorithm with error probability O(n-c) for finding the maximum of n distinct real numbers using only O((log n)2) polynomial tests.link_to_subscribed_fulltex