So do u mean to say that we can leave out those numbers which are less than the median of medians and greater than the median of medians in each round? If yes, I have a case to prove this algo wrong.
-Vijay
On 12/1/05, pramod <[EMAIL PROTECTED]> wrote:
Let M1,M2, ..., MN be the medians and let MM be the median of medians.
So (N-1)/2 medians are less than MM and (N-1)/2 medians are greater
than MM.
Since each of these medians has (N-1)/2 elements less and greater than
themselves within each computer, there are (N-1)/2*(N-1)/2 (this is I
mentioned *around* N^2/4) elements less than MM and same number greater
than MM. What exactly are these numbers is obtained by partitioning.
Overall time complexity is O(N) with all computers running parallel
since each step takes O(N) time.
