Finding an approximate maximum

N. Alon, Y. Azar

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


Suppose that there are n elements from a totally ordered domain. The objective is to find, in a minimum possible number of rounds, an element that belongs to the biggest n/2, where in each round one is allowed to ask n binary comparisons. It is shown that log n + Θ(1) rounds are both necessary and sufficient in the best algorithm for this problem.

Original languageEnglish (US)
Pages (from-to)258-267
Number of pages10
JournalSIAM Journal on Computing
Issue number2
StatePublished - 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Finding an approximate maximum'. Together they form a unique fingerprint.

Cite this