Algo: 1 3 77 78 90 2 5 79 81
compare 1 &2 =1 compare 3 &2 =2 and call binary search on 2nd array widot 2 to identify a proper position for 3 and place it there. now arrays 1 2 77 78 90 3 5 79 81 3 and 77= swap + binary compare 3 and 77, swap them find position of 77 in second array and place there. using binary search 1 2 3 78 90 5 77 79 81 78 and 5 = swap + binary search 1 2 3 5 90 77 78 79 81 90 and 77= swap+ binary 1 2 3 5 77 78 79 81 90 ans found O(nlogn) binary search is O(logn) . On Fri, Jul 8, 2011 at 8:29 AM, durgesh kumar <[email protected]> wrote: > > @dumanshu > > > ok ! i got a O(n lgn) finally > > i don know exact complexity > > Let N = size of first array > > Find the first N smallest elements using one pointer in each array > > now swap the list of elements from index 0 to second-pointer in > > second array to first array > > with first_poiner+1 to N in first Array > > now,after swapnig we need to sort both array > > > > > so complexity= n + n log n+ m log m (n is the size of of first array and m > is the size of second array) > . > . . O(n) = (n log n ) or (m log m) > thanks > Durgesh > > -- > 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. > -- 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.
