Linear time bounds for median computations
- 1 January 1972
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 119-124
- https://doi.org/10.1145/800152.804904
Abstract
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: f(i,n) ≤ 103n/18 A lower bound is shown deductively to be: f(i,n) ≥ n+min(i,n−i+l) + [log2(n)] − 4, for 2 ≤ i ≤ n−1, or, for the case of computing medians: f([n/2],n) ≥ 3n/2 − 3Keywords
This publication has 0 references indexed in Scilit: