On Fri, Sep 2, 2011 at 2:09 AM, Don <[email protected]> wrote: > I think that the complexity might even be log(sizeA) where A is the > smaller of the two arrays. > Imagine that you have sizeA = 3 and sizeB = 1,000,000,000. > You know that the median will either be in A, or it will be > B[500,000,000+/-1]. > The binary search will start off by comparing A[1] with > B[500,000,000]. If it does not find the median there, it will narrow > the search down to either A[0] and B[500,000,001] or A[2] and > B[499,999,999]. > Two steps, which is a lot less than O(3+1,000,000,000). > > Jay, I would suggest that you modify your code as follows: > Instead of initializing startB=0 and endB=sizeB > > startB = (sizeA/SizeB)/2; > endB = startB + sizeA; > > Assuming that sizeA <= sizeB, we know that if the median is in B, it > will be in that range. >
+1. Sounds perfect! :-) > > Don > > On Sep 1, 2:27 pm, Jay Mahadeokar <[email protected]> wrote: > > As you can see, each time, we are either discarding 1st half of A or > second > > half of A. Same for B. > > > > So, the total size is getting reduced by factor of 2 every time. So, the > > time is log(N) where N = sizeA + sizeB. I hope it is clear. > > > > On Fri, Sep 2, 2011 at 12:47 AM, Rahul Verma <[email protected] > >wrote: > > > > > > > > > @jay could you please explain that how you know that the complexity is > > > log(sizeA + sizeB). > > > > > If you don't mind then could you please explain it in detail. > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To view this discussion on the web visit > > >https://groups.google.com/d/msg/algogeeks/-/YHMj8hRnKS4J. > > > 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?hl=en. > > > > -- > > Regards, > > -Jay Mahadeokar > > MTech Final Year, CSE. > > IIT Kanpur. > > -- > 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?hl=en. > > -- Regards, -Jay Mahadeokar -- 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?hl=en.
