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 language||English (US)|
|Number of pages||10|
|Journal||SIAM Journal on Computing|
|State||Published - 1989|
All Science Journal Classification (ASJC) codes
- Computer Science(all)