On the Average-Case Complexity of Selecting the kth Best

Andrew Chi-Chih Yao, F. Frances YaoSIAM Journal on Computing 1982 · DOI · OpenReview

Abstract

Let $\bar V_k (n)$ be the minimum average number of pairwise comparisons needed to find the kth largest of n numbers $(k \geqq 2)$, assuming that all $n!$ orderings are equally likely. D. W. Matula proved that, for some absolute constant c, $\bar V_k (n) - n \leqq ck\ln \ln n$ as $n \to \infty $. In the present paper, we show that there exists an absolute constant $c' > 0$ such that $\bar V_k (n) - n \geqq c'k\ln \ln n$ as $n \to \infty $, proving a conjecture of Matula.
BibTeX
@article{yao1982average,
  author = {Andrew Chi-Chih Yao and F. Frances Yao},
  title = {{On the Average-Case Complexity of Selecting the kth Best}},
  journal = {SIAM Journal on Computing},
  year = {1982},
  doi = {10.1137/0211034},
}

Loading related content...

Figure