Fri, 11 Jun 2010 08:37:31 -0700, Andrei Alexandrescu wrote: > 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
Unfortunately I can't remember. It was probably explained in Jaja's book, which I skimmed through when there was the last parallel programming course 7-8 years ago - I only have some notes left.
