search
Log In
50 votes
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)$
in Algorithms
retagged by
13.2k views
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.
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

Answer: A

15 Answers

1 vote

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

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

Hope this helps :)

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

Answer:

Related questions

21 votes
3 answers
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$
asked Nov 15, 2016 in Algorithms jothee 2k views
33 votes
4 answers
2
3.1k views
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$
asked Nov 14, 2016 in Algorithms jothee 3.1k views
26 votes
4 answers
3
5.8k 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 ... 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
asked Sep 23, 2014 in Algorithms Kathleen 5.8k views
34 votes
9 answers
4
5.6k views
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$
asked Sep 22, 2014 in Algorithms Kathleen 5.6k views
...