Triply-Logarithmic Parallel Upper and Lower Bounds for Minimum and Range Minima over Small Domains
✍ Scribed by Omer Berkman; Yossi Matias; Prabhakar Ragde
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 193 KB
- Volume
- 28
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
We consider the problem of computing the minimum of n values, and several w well-known generalizations prefix minima, range minima, and all nearest smaller Ž .
x w x values ANSV for input elements drawn from the integer domain 1 иии s , where s G n. In this article we give simple and efficient algorithms for all of the preceding Ž . 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 prefix 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 s 2 ⍀ Žlog n log log n. . Since, for s at the lower end of this range, Ž . Ž log log n s ⍀ 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.