On the Average-Case Complexity of Selecting the kth Best
Lists
Only you see this
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...