# GATE2005-39

13.2k 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
15
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??
1

1 vote

With out using min Heap ...if we want to do

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)
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)

Hope this helps :)

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 logn (as given in question)

O($nloglogn$)

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.

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) )

## Related questions

1
2k views
We are given $9$ tasks $T_1, T_2, \dots, T_9$. The execution of each task requires one unit of time. We can execute one task at a time. Each task $T_i$ has a profit $P_i$ and a deadline $d_i$. Profit $P_i$ is earned if the task is completed before the end of the $d_i^{th}$ unit ... $} & \text{$7$} & \text{$3$} \\\hline \end{array}$ What is the maximum profit earned? $147$ $165$ $167$ $175$
Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$. Consider the edge $e$ having the minimum weight amongst all those edges that have one ... minimum weighted spanning tree a weighted shortest path from $s$ to $t$ an Euler walk from $s$ to $t$ a Hamiltonian path from $s$ to $t$
We are given $9$ tasks $T_1, T_2, \dots, T_9$. The execution of each task requires one unit of time. We can execute one task at a time. Each task $T_i$ has a profit $P_i$ and a deadline $d_i$. Profit $P_i$ is earned if the task is completed before the end of the ... gives maximum profit? All tasks are completed $T_1$ and $T_6$ are left out $T_1$ and $T_8$ are left out $T_4$ and $T_6$ are left out
Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$. Consider the edge $e$ having the minimum weight amongst all those edges that have one vertex in ... tree of $G$ the weighted shortest path from $s$ to $t$ each path from $s$ to $t$ the weighted longest path from $s$ to $t$