1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.