Quick links

On Selecting the Second Largest with Median Tests

Report ID:
TR-121-87
Authors:
Date:
October 1987
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.

Follow us: Facebook Twitter Linkedin