how does ur algo produce sorted elements in final array?
On Jul 16, 3:55 pm, Ankur Khurana wrote:
> oops , didnt see the unsorted thing. complexity is mnlog(n) + mn log(m)
>
>
>
>
>
>
>
> On Sat, Jul 16, 2011 at 4:23 PM, sagar pareek wrote:
> > sort all the arrays first O(nlogn)
>
> > then use merge sort
>
> > On Sat, Jul 16, 2011 at 3:43 PM, Ankur Khurana
> > 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 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 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
> > 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 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.
