The Gateway to Computer Science Excellence
+1 vote
501 views

Suppose there are $\log_n$ sorted lists of n $\log_n$ element each. The time complexity of producing a sorted list  of all these elements is (use heap data structure)

  1. $O (n \log \log_n)$
  2. $\theta (n \log_n)$
  3. $\Omega (n \log_n)$
  4. $\Omega (n^{3/2})$
in Algorithms by Veteran (105k points)
retagged by | 501 views

1 Answer

0 votes

We can merge arrays in O($nk\log k$) time using Min Heap. Following is detailed algorithm.

1. Create an output array of size n*k.
2. Create a min heap of size k and insert 1st element in all the arrays into a the heap
3. Repeat following steps n*k times.
     a) Get minimum element from heap (minimum is always at root) and store it in output array.
     b) Replace heap root with next element from the array from which the element is extracted. If the array doesn’t have any more elements, then replace root with infinite. After replacing the root, heapify the tree.

 

Time complexity of producing a sorted list of all these element=O($nk\log k$)

Here K= $\log n$

n=$n\log n$

Time complexity of producing a sorted list of all these element=

O($nk\log k$)=O$(n\log n\log n\log \log n)$

 

Hence,none of these.

 

by Boss (41k points)
edited by
0
will u  plz elaborate how n= n/logn
0
sry it was n Log n.
0
as per ugc net published key option A is correct 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
50,647 questions
56,497 answers
195,489 comments
100,803 users