BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-79-737
       ENTRY:: June 19, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: On the average-case complexity of selecting the k-th best
        TYPE:: Technical Report
      AUTHOR:: Yao, Andrew C.
      AUTHOR:: Yao, F. Frances
        DATE:: April 1979
       PAGES:: 48
    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.
       NOTES:: [Adminitrivia V1/Prg/19950619]
         END:: STAN//CS-TR-79-737