New upper and lower bounds are presented for the maximum number of comparisons, f(i,n), required to select the i-th largest of n numbers. An upper bound is found, by an analysis of a new selection algorithm, to be a linear function of n:
No takes yet. Share an insight, caveat, or question.
Blum et al. (1972) studied this question.