Finding an approximate maximum

N. Alon, Y. Azar

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

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
Volume18
Issue number2
DOIs
StatePublished - 1989

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

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

Cite this