retagged by
26,134 views
75 votes
75 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)

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

15 Answers

1 votes
1 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

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

Answer:

Related questions