Parallel Selection

Authors

Yossi Azar, Tel Aviv University
Nicholas Pippenger, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1990

Abstract

Using the parallel comparison tree model of Valiant, we study the time required in the worst case to select the median of n elements with p processors. With a miniscule improvement of recent work by Ajtai, Komlós, Steiger and Szemerédi, we show that it is [image of equation]* for [image of equation]. This expression is equivalent to one established by Kruskal as the time required to merge two lists of n/2 elements with p processors and, rather curiously, includes as a sub-expression [image of equation] established by Azar and Vishkin as the time required to sort n elements with p processors.

*Image was removed for formatting purposes.

Rights Information

© 1990 Elsevier Ltd.

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

DOI

10.1016/0166-218X(90)90128-Y

Recommended Citation

Yossi Azar, Nicholas Pippenger, Parallel selection, Discrete Applied Mathematics, Volume 27, Issues 1–2, May 1990, Pages 49-58, ISSN 0166-218X, 10.1016/0166-218X(90)90128-Y. (http://www.sciencedirect.com/science/article/pii/0166218X9090128Y)