This is how i think it could be done: (assuming you know the range of elements)
- Divide the whole range of elements into sub ranges. - Iterate through all the arrays and get the no. of elements in each range. - From this you can get a subrange of elements in which your median would fall. - From each array extract the elements which fall in that range. - Now do a merge on the extracted arrays till you get the ith element, where i = k - no.of elements before this subrange. The advantage of this method is that a lot of computation can be done on the client side and very little data needs to be transfered across machines. The complexity of this algo is O(n). Is there a O(log N) algo for this? The algo's proposed look O(N log N). --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
