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.

http://i.stanford.edu/pub/cstr/reports/cs/tr/79/737/CS-TR-79-737.pdf