Parallel algorithm for finding the maximum in $O(\log \log n)$ time

Question

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:

1. If $n = O(1)$, solve the problem trivially;
2. 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;
3. 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?

Answer 1

Each processor gets $\log\log n$ elements, and finds the maximum in time $O(\log\log n)$. Now run the existing algorithm.