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?