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

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?

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