Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

TR-138-88
On Selecting the k Largest with Median Tests
Authors: Yao, Andrew Chi-Chih
Date:March 1988
Pages:10
Download Formats: [PDF]
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.