Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > COMPARISON ALGORITHMS:
Reports tagged with Comparison Algorithms:
TR95-031 | 25th June 1995
Dorit Dor, Uri Zwick

Selecting the median

Improving a long standing result of Sch\"{o}nhage, Paterson
and Pippenger we show that the MEDIAN of a set containing n
elements can always be found using at most 2.95n comparisons.

This is the full version of the paper. An extended abstract
version ... more >>>




ISSN 1433-8092 | Imprint