With a CRCW (Concurrent Read, Concurrent Write) PRAM model, it is possible to find the maximum in an array containing $n$ elements with $n$ processors in $O(\log \log n)$ time. The algorithm is:
- If $n = O(1)$, solve the problem trivially;
- Split the array into $\sqrt n$ parts of equal sizes. Give each part $\sqrt n$ processors and recursively use this algorithm to find maxima on these parts;
- Use all $n$ processors to find the overall maximum among the $\sqrt n$ local maxima in $O(1)$.
Because this algorithm uses $n$ processors, it is not work-optimal. But it seems that there does exist a work-optimal algorithm that has $O(\log \log n)$ time complexity while only using $\frac{n}{\log \log n}$ CRCW processors. However I can't have any clue about how this algorithm works. Is there any idea?