oops , didnt see the unsorted thing. complexity is mnlog(n) + mn log(m) On Sat, Jul 16, 2011 at 4:23 PM, sagar pareek <[email protected]> wrote:
> sort all the arrays first O(nlogn) > > then use merge sort > > > On Sat, Jul 16, 2011 at 3:43 PM, Ankur Khurana > <[email protected]>wrote: > >> Use divide and conquer. take 2 array at a time and .so you are merging two >> array at a time. >> >> num_of_list=m; >> length of list=n; >> >> while(num_of_list > 1) >> { >> while( (num of list where length = length_of_list) >2) >> { >> merge two lists of length (length_of_list); >> >> } >> if(num_of_list %2==0) >> num_of_list/=2; >> else >> num_of_list/=2+1; >> length of list=n; >> >> } >> (it is just a general idea , you have to take care of the left over list >> every time , the check for that i havent posted) >> >> so time complexity is >> >> >> 2*n* (m/2) + 2* 2n* (m/4) .............. log(m) times. >> >> so complexity is n*m*log(m) >> >> >> >> >> >> On Sat, Jul 16, 2011 at 2:43 PM, aseem garg <[email protected]> wrote: >> >>> Q2. Given m arrays of n size each, give an algorithm to combine these >>> arrays into a single array with sorted elements. Also tell the time >>> complexity of your solution. >>> Aseem >>> >>> -- >>> 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 > SAGAR PAREEK > COMPUTER SCIENCE AND ENGINEERING > NIT ALLAHABAD > > -- > 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.
