Summary: We consider the problem of computing the minimum of \(n\) values, and several well-known generalizations (prefix minima, range minima, and all-nearest-smaller-values (ANSV) problems) for input elements drawn from the integer domain \([1.. s]\) where \(s \geq n\). Recent work [O. Berkman et al., SIAM J. Comput. 23, No. 3, 449–465 (1994; Zbl 0938.68659)] has shown that parallel algorithms that are sensitive to the size of the input domain can improve on more general parallel algorithms. The cited paper demonstrates an \(O(\log \log \log s)\)-step algorithm on an \(n\)-processor Priority CRCW PRAM for finding the prefix-minima of \(n\) numbers in the range \([1..s]\). The best known upper bounds for the range minima and ANSV problems were previously \(O(\log \log n)\) (using algorithms for general input). This was also the best known upper bound for computing prefix minima or even just the minimum on the Common CRCW PRAM; this model has a \(\Theta (\log n/ \log \log n)\) time separation from the stronger Priority model when using the same number of processors. In this paper we give simple and efficient algorithms for all of the above problems. These algorithms all take \(O(\log \log \log s)\) time using an optimal number of processors and \(O(ns)^\epsilon\) space on the Common CRCW PRAM. We also prove a lower bound demonstrating that no algorithm is asymptotically faster as a function of \(s\), by showing that for \(s = 2^{2^{\Omega (\log n \log \log n)} }\) the upper bounds are tight.
For the entire collection see [Zbl 0825.00122].