Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR95-031 | 25th June 1995 00:00

Selecting the median

RSS-Feed




TR95-031
Authors: Dorit Dor, Uri Zwick
Publication: 26th June 1995 13:03
Downloads: 1036
Keywords: 


Abstract:

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 of the paper apperead in the proceedings SODA'95.



ISSN 1433-8092 | Imprint