On Selecting the k Largest with Median Tests

Abstract:

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.