Let the common computer be called Master and others be called slaves.
1. The master maintains a min-priority queue and asks for the smallest number from each slave. It then deques one number from the queue and asks for the next smallest number from the slave which originally holds the dequed number and inserts the new number into min-priority queue. This it will keep on doing for (N^2-1)/2 times. The N^2/2-th number dequed from the queue is going to be the median.
The complexity is O(N^2).
2. The master asks for the minimum and maximum number from each slave and determines the global min and global max. Now from the range R, it calculates the average (min + max)/2. Let it be M. It now asks each slave how many numbers in their set are less than M? If the total adds to N^2/2 (Lets call it T), then M is the median. If T>N^2/2, then median lies between min and M. So we find the average of min and N and carry out same procedure till we get the answer. If T<N^2/2, then median lies between M and max. (This is something like binary search).
The complexity is N lg R. (R is the range).
Clearly the second method is better if range is not too high.
Both the algos use O(n) space.
~Vishal
On 12/3/05,
pramod <[EMAIL PROTECTED]> wrote:
In my algo, this O(N) space restriction is not violated. Each computer
uses O(N) space only. But overall, all the N computers use O(N^2) space.
--
Vishal Padwal
-----------------------------------
Master of Science
Computer Science Dept.
Stony Brook University
Stony Brook, NY
Tel : 631-645-1406
