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. 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.
