TRIPLY-LOGARITHMIC PARALLEL UPPER AND LOWER BOUNDS FOR MINIMUM AND RANGE MINIMA OVER SMALL DOMAINS

We consider the problem of computing the minimum of n values, and seve ral well-known generalizations [prefix minima, range minima, and all n earest smaller values (ANSV)] for input elements drawn from the intege r domain [1 ... s], where s greater than or equal to n. In this articl e we give simple and efficient algorithms for ail of the preceding pro blems. These algorithms all take O(logloglog s) time using an optimal number of processors and O(ns(epsilon)) space (for constant epsilon < 1) On the COMMON CRCW PRAM. The best known upper bounds for the range minima and ANSV problems were previously O(loglog n) (using algorithms for unbounded domains). For the prefix minima and for the minimum pro blems, the improvement is with regard to the model of computation. We also prove a lower bound of n(loglog n) for domain size s=2(Omega(log n log log n)). Since, for s at the lower end of this range, log log n = Omega(logloglog s), this demonstrates that any algorithm running in o(log loglog s) time must restrict the range of s on which it works, ( C) 1998 Academic Press.