Linear time bounds for median computations

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 < 5.73n, for 1 ≤ i ≤ n. 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 − 3

REFERENCES

• 1: Ford, Lester R. and Selmer M. Johnson. ";A Tournament Problem."; American Math. Monthly, Vol. 66, No. 5 (May, 1959).
• 2: Hadian, Abdollah, and Milton Sobel. ";Selecting the t-th largest using binary errorless comparisons."; Technical Report 121, Dept. of Statistics, University of Minnesota. (May, 1969), 15 pp.
• 3: C. A. R. Hoare, Algorithm 65: find, Communications of the ACM, v.4 n.7, p.321-322, July 1961 [doi>10.1145/366622.366647]
• 4: Kislitsin, S. S. ";On the selection of the k-th element of an ordered set by pairwise comparisons."; Sibirsk. Math 5 (1964), 557-;564. (MR. 29, No. 2198).
• 5: Schrcier, Josef. Mathesis Polska 7 (1932), pp. 154-;160.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Theory