@aman: wat u dint get??? On Fri, Jul 8, 2011 at 6:34 PM, Aman Goyal <[email protected]> wrote:
> 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. > -- 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.
