An efficient parallel algorithm for the single function coarsest partitionproblem on the EREW PRAM

In this paper, we derive an efficient parallel algorithm to solve the singl e function coarsest partition problem. This algorithm runs in O(log(2)n) ti me using O(nlogn) operations on the EREW PRAM with O(n) memory cells used. Compared,vith the previous PRAM algorithms that consume O(n(1+epsilon)) mem ory cells for some positive constant epsilon >0, our algorithm consumes les s memory cells without increasing the total number of operations.