11
$\begingroup$

We were presented in class with an algorithm for finding the maximum in an array in parallel in $O(1)$ time complexity with $n^2$ computers.

The algorithm was:

Given an array A of length n:

  1. Make a flag array B of length n and initialize it with zeroes with $n$ computers.
  2. Compare every 2 elements and write 1 in B at the index of the minimum with $n^2$ computers.
  3. Find the index with the 0 in A with $n$ computers.

The lecturer teased us it could be done with $\frac{n}{\log n}$ computers and with $\log n$ time complexity.

After a lot of thinking I couldn't figure out how to do it. Any idea?

Improve this question
$\endgroup$
1
  • $\begingroup$ This assumes a CRCW computer. $\endgroup$ Commented Oct 20, 2022 at 10:31

1 Answer 1

Reset to default
9
$\begingroup$

Divide your original array into $n/\log n$ blocks of length $\log n$. Put each processor in charge of each block, and find the maximum using the usual algorithm in time $\log n$. We now need to compute the maximum of an array of length $n/\log n$. Pair up the elements and compute the pairwise maxima to reduce the size of the array by a half. Repeat it $\log n$ times to find the maximum of the entire array.

The same idea also shows that you can compute the maximum in parallel in constant time using $n^{1+\epsilon}$ computers for every $\epsilon > 0$. (Exercise.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ The goal was to find a maximum in $O(1)$ time, not $O(\log{n})$ $\endgroup$ Commented Feb 24, 2014 at 14:43
  • $\begingroup$ Take it upon yourself to prove a lower bound of $\Omega(n)$ for the number of computers multiplied by the time complexity. $\endgroup$ Commented Feb 24, 2014 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.