On Selecting the Second Largest with Median Tests
Report ID: TR-121-87Author: Yao, Andrew
Date: 1987-11-00
Pages: 11
Download Formats: |PDF|
Abstract:
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.