@sharad in the first step you will have to merge k lists each of n size ..
you will mwrge 2 at a time wouldn't that be O(n*k/2)
so t(n)=n(k/2)+n(k/4)+......................
correct me if i'm wrong anyways
On Sun, Jul 4, 2010 at 9:56 AM, Dave <dave_and_da...@juno.com> wrote:
>
> @Sharad. Haven't you changed the roles of n and k? The original poster
> had n lists with average length k, meaning a total of n*k elements.
> You have k lists with a total of n elements, meaning that each list
> has an average of n/k elements.
>
> Dave
>
> On Jul 3, 1:02 pm, sharad kumar <sharad20073...@gmail.com> wrote:
> > 1. First take two lists at a time and merge them so total elements parsed
> > for all lists =O(n)
> > This operation results in k/2 lists
> > 2. Repeat steps till k/2 == 1.
> >
> > *Time complexity of above solution = O(n logk)*
> > Step1 would loop through *logk *times and each operation would require
> > parsing all n elements in all the lists for making k/2 lists
> >
> > eg:: if i had 8 lists then first pass would make 4 lists by parsing all n
> > elements; second pass would make 2 lists by parsing again n elements and
> > third pass would give 1 list again by parsing n elements.
> >
> > *Constraint of the above Solution*
> > For merging we would require *O(n) *extra space.
> >
> > *Solution2: Without Using O(n) extra space; uses O(k) extra space*
> > **j = 1;
> > 1. (For all lists L[i])
> > {
> > Take the jth element from each list and create a min heap in O(k) with
> the
> > node data and
> > index information. Take the minimum element from the heap in O(1) i.e.
> root
> > node and put
> > it in *List1 indexj.*
> > **if the element didn't belong to list1[j] then swap it with list1[j]
> with
> > list to which the min
> > element belonged.
> > Now increment the pointer j for the list l1(or to the list where in the
> min
> > nodes are getting added) and add the new node to min heap}
> >
> > 2. Keep repeating steps 1 till all n elements are being looked up
> >
> > *Time Complexity = O(n logk ) SPACE = O(k)*
> > At a time we have k elements min heap and for all n elements we have to
> > readjust the heap in log(k) time so total time = *O(n logk )* and space
> used
> > = *O(k)*
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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.
