On selecting the k largest with median tests (Q1115626)

Let \(W_ k(n)\) be the minimax complexity of selecting the k largest elements of n numbers \(x_ 1,x_ 2,...,x_ n\) by pairwise comparisons \(x_ i:x_ j\). It is well known \(W_ 2(n)=n-2+[lg n],\) and \(W_ k(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 \(x_ i\) the median of \(\{x_ i,x_ j,x_ t\}?''\) are also allowed. It is proved that \(W_ 2'(n)=n-2+\lceil lg n\rceil,\) and \(W_ k'(n)=n+(k-1)lg_ 2 n+O(1)\) for all fixed \(k\geq 3\).