|
TR-138-88
On Selecting the k Largest with Median Tests |
|
| Authors: | Yao, Andrew Chi-Chih |
| Date: | March 1988 |
| Pages: | 9 |
| Download Formats: | |
Let Wk(n) be the minimax complexity of selecting the k largest elements of n numbers x1, x2, ..., xn by pairwise comparisons xi : xj. It is well known that W2(n) = n-2+[lgn], and Wk(n) = n + (k - 1) lg n +O(1) for all fixed k geq 3. In this paper we study W'k(n), the minimax complexity of selecting the k largest, when tests of the form "Is xi the median of {xi; xj; xt}?" are also allowed. It is proved that W'2(n) = n + (k - 1) lg2 n + O(1) for all k geq 3. |
|