The Gateway to Computer Science Excellence
+42 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)$
in Algorithms by Boss (17.5k points)
retagged by | 7.5k views
Refer this for better understanding of question.
plzz correct the question.  size of each sorted list is n/logn..?
The merge is two-way merge.
what is this ??
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..
Question say use heap data structure why people are using k way merge sort??

Answer: A

12 Answers

+1 vote

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

by (93 points)
0 votes
O(N loglogN)
by (175 points)
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)
by (21 points)
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)
by Active (4.1k points)

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
50,737 questions
57,312 answers
105,036 users