The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
4.1k 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)$
asked in Algorithms by Boss (18k points)
retagged by | 4.1k views
+3
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
+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

7 Answers

+42 votes
Best answer
Since we have $\log n$ lists we can make a min-heap of $\log n$ elements by taking the first element from each of the $\log n$ sorted lists. Now, we start deleting the min-element from the heap and put the next element from the sorted list from which that element was added to the heap. (This identity can be done by making a structure of two values, one for the number and one for identifying the origin sorted list of that number and storing this structure in the heap). In this way each delete and the corresponding insert will take $O(\log\log n)$ time as delete in heap of size $n$ is $O(\log n)$ and inserting an element on a heap of size $n$ is also $O(\log n)$. (here, heap size is $\log n$). Now, we have a total of $\log n \times \frac{n}{\log n} = n$ elements. So, total time will be $O(n \log\log n)$.
answered by Boss (18k points)
selected by
0
How the deletion in heap takes O(1) time? Can you please explain? I think it should be O(log n) (if no. of elements are n) in this case it will be O(log log n) although the answer will still remain same.
0

Sorry Arjun Sir, but I am bit confused in it.

Yes,  Saurabh is right that to preserve heap property, taking out min element will take O(logN) time ( so here it is loglogn ). But how this deletion is actually working here in this question??

1. We have created min-heap with O(log n) by considering the first element in each sorted list

2. In order to take out min element (deleting) will be down by swapping min with last element... So, here are we swapping the entire two nodes or just 2 elements???? It cannot be elements, because then sorted order cannot be maintained in each node AND how can it even be entire node swap? because after swap, in order to delete min element ( which is start of the list) we have to take it to the last through n/log(n) elements (or shift rest of the list to left by 1 position) and the go for preserving the heap property. So, answer will change in this case. (Kindly note that, if we ignore this fact on shifting.. Then I am getting the correct answer as nloglog(n) )

Can you clarify where am I going wrong??

+1

u can use merge sort also.

deletion is O(loglogn)

+1
Sir if we have 2 sorted lists containing m and n elements then we can merge it using merge procedure from merge sort in O(m+n) so here if we have k sorted lists containing e elements then we can merge it in O(ke) which would be O(logn * (n/logn)) = O(n). So why not use this ?
0
Creation of heap is fine , but at the end sorted list is required ... dig little bit more approach is fine.....
+1

Same kind question , if do by heap sort or merge sort

https://gateoverflow.in/46595/cmi2013-a-05

0
@Saurabh & @Tushar ....

heapify takes O(log n) and deletion takes of any element O(n) , you guys are right !!! BUT there is a "but"...

HERE YOU ARE DELETING THE MINIMUM ELEMENT FROM THE MIN HEAP which takes O(1) :-)
+8 votes

We can merge x arrays of each size y in in O(xy*Logy) time using Min Heap.

x = n/Logn
y = Logn

We get O(n/Logn * Logn * Log Log n) which is O(nLogLogn)

answered by Active (4.2k points)
+1
in question , number of elements in each lis is n/logn

so y = n/logn
0
0(xy*logx ) will satisfy because we can merge x arrays of each size y in0(xy*logx)..
+7 votes

This may help!!!

answered by (161 points)
+6 votes
Number of  List = Log(n) , Number of elements in each list = n/Log(n)

Take the pair appraoch( like merge in pairs , (1,2) is first pair  , (3,4) is the second pair , (4,5) , (6,7)...... (log(n) - 1,logn) will be the log(n)/2 th pair and merge using merge procedure of mergesort which takes Theta(k) where k is the number of elements in big one list.

Thus for first attempt the work will be [ ( n/log(n) ) *  ( log(n)/2 ) ]= n/2  as theta(n/log(n)) work has to be done for each pair and total log(n)/2 pairs are there

Second attempt , as now we have ( log(n)/2 ) list so again make pairs but now element in each list is 2n/log(n)

thus work will be =>  ( 2n/logn) * (log(n)/4 )  = n/2

similliarly again number of list will be half then make pairs thus for third attempt work will

be  = (4n/logn) * (log(n)/8)  = n/2

and so on....

total log(logn) attempt will be there , after that we will get single list of n elements

Thus (n/2 + n/2 + n/2 + ....... log(logn) terms )

thus ans = (n/2)* ( log(logn) ) = n log(logn)
answered by (101 points)
edited by
+1 vote
Lets start with 2 list each of size n

to merge them we will need, O( n+n ) = O (2n)

similarly to merge k list of size n = O ( kn )

Now to merge log(n) lists of size n/log(n)

it will take   O ( log(n) * n / log(n)  ) = O ( n )
answered by Active (3.5k points)
0
Merging 2 lists of size n will take O(n) , that's fine, but the question is on two - way merge (sorry i did not mention it before) so we have to merge lists multiple times rather than just merging lists once.

If merge was to be done only once it would be O(n).
This is my understanding of the question, please correct me if I am wrong.
0

ya you are also making a good point here,

for first merge its  = O ( 2n )

second = O ( 3n )

ans so on for (k-1)th merge = O ( kn )

---------------------------------------------

in total = O ( 2n  + 3n + ......+ kn ) = O ( k2 n )

so in case of this question = O ( log2(n) * n / log(n) ) = O ( n * log(n) )

0

Yes.. 
Actually I got the same answer as you when I solved it myself, O(n* log (n) ) ,
but the correct answer given is O(n * log(log (n) ) ).  Couldn't reach this one, but from the approach, O(n log n ) seems right.

0 votes

If we have n lists, each consisting of m integers sorted in ascending order. Merging these lists into a single sorted list will take time:

  • O(mnlogn)

As here n=log n and m=n/logn

O((n / logn )*log n)log logn = O (n log log n)

More Reference

https://gateoverflow.in/46595/cmi2013-a-05

answered by Active (4.4k points)
–1 vote
O(N loglogN)
answered by (165 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,112 questions
44,694 answers
127,237 comments
43,753 users