On selecting the k largest with median tests

Let W _itk(n) be the minimax complexity of selecting the k largest elements of n numbers x ₁, x ₂,..., x _n by pairwise comparisons x _i :x _j . It is well known that W ₂(n) =n-2+ [lg n], and W _k (n) = n + (k-1)lg n +O(1) for all fixed k ≥ 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′₂(n) =n-2+ [lg n], and W′ _k (n) =n + (k-1)lg₂ n +O(1) for all fixed k≥3.