On the average-case complexity of selecting k-th best

1 October 1978

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

No. 02725428,p. 280-289
https://doi.org/10.1109/sfcs.1978.29

Abstract

Let Vk (n) be the minimum average number of pairwise comparisons needed to find the k-th largest of n numbers (k≥2), assuming that all n! orderings are equally likely. D. W. Matula proved that, for some absolute constant c, Vk(n)- n ≤ ck log log n as n → ∞. In the present paper, we show that there exists an absolute constant c′ ≫ 0 such that Vk(n) - n ≥ c′k log log n as n → ∞, proving a conjecture by Matula.

Keywords

DECISION TREES
COSTS
COMPUTER SCIENCE
CONSTRAINT THEORY
BINARY TREES

This publication has 3 references indexed in Scilit:

Bounds for Selection
SIAM Journal on Computing, 1976
Expected time bounds for selection
Communications of the ACM, 1975
On lower bounds for computing the i-th largest element
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1973