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 language | English (US) |
|---|---|
| Pages (from-to) | 258-267 |
| Number of pages | 10 |
| Journal | SIAM Journal on Computing |
| Volume | 18 |
| Issue number | 2 |
| DOIs | |
| State | Published - 1989 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- General Computer Science
- General Mathematics