D.S. Turaga, K. Ratakonda, et al.
SCC 2006
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 Θ n p+log logn log(1+ p n) for 1≤p≤( n 2). 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 Θ logn log(1+ p n) established by Azar and Vishkin as the time required to sort n elements with p processors. © 1990.
D.S. Turaga, K. Ratakonda, et al.
SCC 2006
Minghong Fang, Zifan Zhang, et al.
CCS 2024
Moutaz Fakhry, Yuri Granik, et al.
SPIE Photomask Technology + EUV Lithography 2011
Mario Blaum, John L. Fan, et al.
IEEE International Symposium on Information Theory - Proceedings