# Parallel algorithm for finding the maximum in $\log n$ time using $n / \log n$ processors

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 alot of thinking I couldn't figure out how to do it. Any idea?

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.)
• The goal was to find a maximum in $O(1)$ time, not $O(\log{n})$ – NightRa Feb 24 '14 at 14:43
• Take it upon yourself to prove a lower bound of $\Omega(n)$ for the number of computers multiplied by the time complexity. – Yuval Filmus Feb 24 '14 at 14:47