@aman: Let size of *first array be m* and that of the *second array be* *n*.
For m elements in first array you perform binary search therefore time O(mlogn) And for those some elements of the first array you perform shifting in array two...in the worst case for all the elements of first array you might have to perform shifting in second array and also you might just have to shift all the present (n-1) elements each time...so again in worst case this whole procedure will take O(mn) time.... so total coplexity of your idea is: O(mlogn) + O(mn) And if m is of the O(n) then this will take O(n^2) time in worst case. On Fri, Jul 8, 2011 at 2:40 PM, Aman Goyal <aman.goya...@gmail.com> wrote: > 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 <durgesh1...@gmail.com>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 algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
