Finding the Median

Authors

Arnold Schönhage, University of Tübingen, Germany
Mike Paterson, University of Warwick
Nicholas Pippenger, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1976

Abstract

An algorithm is described which determines the median of n elements using in the worst case a number of comparisons asymptotic to 3n.

Rights Information

© 1976 Elsevier Ltd.

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

DOI

10.1016/S0022-0000(76)80029-3

Recommended Citation

A. Schönhage, M. Paterson, N. Pippenger, Finding the median, Journal of Computer and System Sciences, Volume 13, Issue 2, October 1976, Pages 184-199, ISSN 0022-0000, 10.1016/S0022-0000(76)80029-3. (http://www.sciencedirect.com/science/article/pii/S0022000076800293)