retard wrote:
First, divide the problem into log(log(n)) blocks and solve them sequentially, the complexity is O(log log n), because the problem size is log(log(n)) and the sequential algorithm works in O(n). Then, use a divide and conquer algorithm for the n/log(log(n)) maximums obtained from the blocks. With the correct algorithm this stage is also O(log log n), thus the overall complexity is O(log log n). And yes, it assumes you have n/log(log(n)) cores.
What is the correct algorithm for the second stage? Do you have a reference at hand?
Andrei
