According to the problem there should be 'n * k' elements in all (on an average). For merging all the elements into a single list one has to look at all the elements at least once. (For eg in case of merging two lists of size n1 and n2, the worst case complexity in O(n1 + n2)).
Extending to the multiple lists the complexity should be O(n k) atleast. We can merge two lists at a time. Say list1 and list 2 , list 3 and list 4 and so on... After this operation we will have (n/2) lists with 2k elements each. The time complexity of this set of merges in = (n/2) * (k + k) = nk. Now in the second pass (merging the resulting 2k length lists pairwise), we will have time complexity of (n/4) * (2k + 2k) = nk. Proceeding like this we will have , log n sets (passes) of merges. So complexity is O(nk log n). I have a gut feel that this should be the best we can do. Because if k = 1, we essentially have n single element lists. Merging them into one single list is equal to sorting them. For which the lower bound in n log n. On Sat, Jul 3, 2010 at 11:06, divya <sweetdivya....@gmail.com> wrote: > How do you merge n sorted lists with average length K in O(n*log(K)) > time? > > -- > 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. > > -- 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.
