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: (Equation presented), A lower bound is shown deductively to be: (Equation presented), or, for the case of computing medians: (Equation presented).
|Original language||English (US)|
|Number of pages||6|
|Journal||Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - May 1 1972|
|Event||4th Annual ACM Symposium on Theory of Computing, STOC 1972 - Denver, United States|
Duration: May 1 1972 → May 3 1972
All Science Journal Classification (ASJC) codes