Report Number: CS-TR-79-737
Institution: Stanford University, Department of Computer Science
Title: On the average-case complexity of selecting the k-th best
Author: Yao, Andrew C.
Author: Yao, F. Frances
Date: April 1979
Abstract: Let ${\bar{V}}_k$(n) be the minimum average number of pairwise comparisons needed to find the k-th largest of n numbers (k $\leq$ 2), assuming that all n! orderings are equally likely. D. W. Matula proved that, for some absolute constant c, ${\bar{V}}_k$(n)-n $\leq$ c k log log n as n $\rightarrow \infty$. In the present paper, we show that there exists an absolute constant c' > 0 such that ${\bar{V}}_k$(n)-n $\leq$ c' k log log n as n $\rightarrow \infty$, proving a conjecture of Matula.