aj wrote:
> How about finding the median of (X + Y) in subquadratic time.
> X + Y = {z | z = xi + yj for some i and j}.
>
> I could only reduce the space complexity from O(n^2) to O(n) but time
> complexity still
> remains O(n^2).
>
> thx
> Aj
Can't you merge the two sorted array in O(n) into a single sorted
array, then the median is just the "middle" of the single array?
I don't understand the notation:
X + Y = {z | z = xi + yj for some i and j}.
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
