7.5k views

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)

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

retagged | 7.5k views
+11
Refer this for better understanding of question.

http://www.geeksforgeeks.org/merge-k-sorted-arrays/
+1
plzz correct the question.  size of each sorted list is n/logn..?
0
The merge is two-way merge.
0
0
+2
what is this ??
+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..
0
0
Question say use heap data structure why people are using k way merge sort??
0

Answer: A +1 vote

With out using min Heap ...if we want to do by (93 points)
O(N loglogN)
by (175 points)
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)
by (21 points)