Selecting small ranks in EREW PRAM
Given an array of n items from a totally ordered set, we show that the kth smallest element of the array can be found in O(lgn (lg* rr - lg*(n/ k))) time and O(n) work on an EREW PRAM. This means, in particular, that the kth smallest item can be found in O(lg n) time using n/lg n processors on an EREW PRAM as long as k less than or equal to n/lg((c)) n for some constant c. Here Ig((c)) n is the logarithm, iterated c times, of n and lg* n is the number of times the logarithm is taken before the resulting number becomes less than 1. (C) 1999 Elsevier Science B.V. All rights reserved.
selection pram parallel algorithms combinatorial problems