Problem Detail: 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:
- Make a flag array B of length n and initialize it with zeroes with $n$ computers.
- Compare every 2 elements and write 1 in B at the index of the minimum with $n^2$ computers.
- 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?
Asked By : Gil
Answered By : Yuval Filmus
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.)
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/21910
