what means O(n) time ? I don't get...
Vijay Venkat Raghavan N wrote:
Hi pramod,
I dont get the last part of your solution. How does it leave us with
n^2/4 lesser and greater than the median? Also if we leave out
everythng thats lesser or greater than a number, all what should be
left is the number itelf. I am missing something and plz explain your
algo's last part clearly.
Also what is the overall time complexity of the entire procedure?
-Vijay
On 12/1/05, *pramod* <[EMAIL PROTECTED]
<mailto:[EMAIL PROTECTED]>> wrote:
Each computer finds the median of the numbers it holds. This can be
done in O(n) time and O(n) space by each computer. Now all computers
send their median to a dedicated computer which finds the median of
these medians ( O(n) time and space) and sends this value to all the
computers. Each computer in turn partitions the numbers it has (O(n)
time and space) according to this median of medians and sends how many
numbers are less and greater than the median of medians to the
dedicated computer. This leaves us with around n^2/4 numbers less than
the median of median and n^2/4 numbers greater than the median of
medians. So now we need to repeat the process with around n^2/2
elements.
