i dint get you.. one loop to access the first array elements and compare with second array, and one logn (for) loop to binary search the second array , thts it.. O(mlogn) is what i am able to understand.
On Fri, Jul 8, 2011 at 5:52 PM, Apoorve Mohan <[email protected]>wrote: > @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 <[email protected]> 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 <[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. >> > > > > -- > 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 [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.
