http://www.geeksforgeeks.org/merge-k-sorted-arrays/

50 votes

Suppose there are $\lceil \log n \rceil$ sorted lists of $\lfloor n /\log n \rfloor$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint:Use a heap data structure)

- $O(n \log \log n)$
- $\Theta(n \log n)$
- $\Omega(n \log n)$
- $\Omega\left(n^{3/2}\right)$

15

Refer this for better understanding of question.

http://www.geeksforgeeks.org/merge-k-sorted-arrays/

http://www.geeksforgeeks.org/merge-k-sorted-arrays/

1

How can u take " n -nlog(logn)/logn , here we can take as nlog(logn)/logn "???

and this should not be the logic...

Anyone verify this..

and this should not be the logic...

Anyone verify this..

0

Try to solve the following problem -

https://www.interviewbit.com/problems/merge-two-sorted-lists-ii/

https://www.interviewbit.com/problems/merge-two-sorted-lists-ii/

0 votes

We can merge P sorted arrays of each size Q in O(PQ LogP)

P = log n

Q = n/log n

∴ Putting values we get,

O(n log log n)

P = log n

Q = n/log n

∴ Putting values we get,

O(n log log n)

0 votes

I want to solve this problem using tree method.

we have total element = (n/log n)*(log n)=n [ log n list , and each list has n/log n element ]

and height of tree = log ( log n) because we have log n list

So total , it will be = n*log (log n)

we have total element = (n/log n)*(log n)=n [ log n list , and each list has n/log n element ]

and height of tree = log ( log n) because we have log n list

So total , it will be = n*log (log n)

0 votes

This might help.

The most confusing part is how there are __loglogn__ levels, so here is my approach.

The question says we have *logn* sorted list, for me this was difficult to visualize.

so lets take it as “there are **X **sorted lists”, now we know if they were to be sorted

using merge sort a binary tree will be formed.

Now, that tree with **X** elements will have log(**X**) levels.

The question also gives us total number of elements that is $log(n)*n/log(n)= n$

So n comparisons at every level $n*log(X)$ replacing **x** by l*ogn** *(as given in question)

**O**($nloglogn$)

0 votes

Is this the right approach?

Suppose I have n = 7 elements, therefore I have (⌈logn⌉ = 3) heaps with each ( ⌈n/logn⌉ = 2) elements.

Now, for combining all of them into a single heap, I’ll just sort their roots first and build a max heap amongst them(which would take **logn*loglogn + logn **time, logn*loglogn for sorting and other logn for building max heap). And after arranging the roots of all the heaps, I’ll do the same thing for the remaining nodes. And as there are ⌈n/logn⌉ items, the complexity will be **O(n/logn(logn*loglogn + logn)) = O(nloglogn). **Therefore **A is correct.**

0 votes

There are** logn** lists and **n/logn** elements in each list . Lets take one element from each of these** logn **number of list total **logn** elements and provide it to a min heap . We delete and insert in array these** logn** elements which takes **O(log(logn)) **time and since there are total** n elememts( logn * n/logn = n ) **it takes** O( nlog(logn) )** time complexity

Hence answer is **O( nlog(logn) )**