caa a22 4500 469033991 CHVBK 20180323132751.0 cr unu---uuuuu 170328e19921201xx s 000 0 eng 10.1007/BF01200429 doi (NATIONALLICENCE)springer-10.1007/BF01200429 Randomized range-maxima in nearly-constant parallel time [Elektronische Daten] [Omer Berkman, Yossi Matias, Uzi Vishkin] Given an array ofn input numbers, therange-maxima problem is that of preprocessing the data so that queries of the type "what is the maximum value in subarray [i..j]” can be answered quickly using one processor. We present a randomized preprocessing algorithm that runs inO(log* n) time with high probability, using an optimal number of processors on a CRCW PRAM; each query can be processed in constant time by one processor. We also present a randomized algorithm for a parallel comparison model. Using an optimal number of processors, the preprocessing algorithm runs inO(α (n)) time with high probability; each query can be processed inO (α (n)) time by one processor. (As is standard, α(n) is the inverse of Ackermann function.) A constant time query can be achieved by some slowdown in the performance of the preprocessing stage. Birkhäuser Verlag, 1992 parallel algorithms nationallicence randomized algorithms nationallicence PRAM nationallicence comparison model nationallicence range maximum nationallicence prefix maximum nationallicence 68Q20 nationallicence Berkman Omer Dept. of Computer Science, King's College London, Strand, WC2R 2LS, London, ENGLAND aut Matias Yossi Institute for Advanced Computer Studies, University of Maryland, 20742, College Park, MD, USA aut Vishkin Uzi Dept. of Computer Science, Tel Aviv University, ISRAEL aut computational complexity Birkhäuser-Verlag 2/4(1992-12-01), 350-373 1016-3328 2:4<350 1992 2 37 https://doi.org/10.1007/BF01200429 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01200429 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Berkman Omer Dept. of Computer Science, King's College London, Strand, WC2R 2LS, London, ENGLAND aut NATIONALLICENCE 700 1- Matias Yossi Institute for Advanced Computer Studies, University of Maryland, 20742, College Park, MD, USA aut NATIONALLICENCE 700 1- Vishkin Uzi Dept. of Computer Science, Tel Aviv University, ISRAEL aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag 2/4(1992-12-01), 350-373 1016-3328 2:4<350 1992 2 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer