Treffer: Triply-logarithmic parallel upper and lower bounds for minimum and range minima over small domains

s] where s n. 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) space (for constant <1) on the common crcw pram. The best known upper bounds for the range minima and ansv problems were previously O(log log n) (using algorithms for unbounded domains). For the pre x minima and for the minimum problems, the improvement is with regard to the model of computation. We also prove a lower bound of (log log n) for domain size s =2 Since, for s at the lower end of this range, log log n = 2 (log n log log n) (log log log s), this demonstrates that any algorithm running in o(log log log s) time must restrict the range of s on which it works.