A RANDOMIZED ALGORITHM FOR FINDING MAXIMUM WITH O((LOG N)(2)) POLYNOMIAL TESTS

Authors
TING HF YAO AC
Citation
Hf. Ting et Ac. Yao, A RANDOMIZED ALGORITHM FOR FINDING MAXIMUM WITH O((LOG N)(2)) POLYNOMIAL TESTS, Information processing letters, 49(1), 1994, pp. 39-43
Citations number
1
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
49
Issue
1
Year of publication
1994
Pages
39 - 43
Database
ISI
SICI code
0020-0190(1994)49:1<39:ARAFFM>2.0.ZU;2-J
Abstract
A well-known result by Rabin implies that n - 1 polynomial tests are n ecessary and sufficient in the worst case to find the maximum of n dis tinct 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.