|
TR-121-87
On Selecting the Second Largest with Median Tests |
|
| Authors: | Yao, Andrew Chi-Chih |
| Date: | November 1987 |
| Pages: | 10 |
| Download Formats: | |
Let Vk(n) be the minimas complexity of selecting the k - th largest of n numbers x1, x2,..., xn by pairwise comparisons xi : xj. It is well known that V2(n) = n 2 + [lg n]. In this paper we study V'2 (n), the minimax complexity of selecting the second largest, when tests of the form "Is xi the median of {xi, xj, xk}?" are also allowed. It is proved that n-3+[lg n] leq V'2(n) leq n-2+[lg n]. Furthermore, both upper and lower bounds are achieved for infinitely many n. |
|