retagged by
689 views
0 votes
0 votes
Suppose there are k sorted lists (decreasing order) with n/k elements in each list.

What is the time complexity to merge them into one single sorted list.

Hint: Maintain a heap of k elements. Think which k elements to choose.

 

A. O(nlogk)

B. O(n)

C. O(nk)

D. O(nlogn)
retagged by

3 Answers

2 votes
2 votes

Option A should be TRUE

i don’t know why it is unchecked for correction for almost an year

0 votes
0 votes

D. O(nlogn)...

 

Hence the total time for merge Sort function will become n(log n + 1) , which gives us a time complexity of O(n*log n) …

Time complexity of Merge Sort is O(n*Log n) in all the 3 cases (worst, average and best) as merge sort always divides the array in two halves and takes linear time to merge two halves...

 

1. https://gateoverflow.in/16103/The-time-complexity-of-producing-a-sorted-list

 

 

0 votes
0 votes
T(n) = O(nlogk)

option A

Related questions

1 votes
1 votes
1 answer
3
rsansiya111 asked Dec 7, 2021
315 views
In an array A[1..n] of n distinct elements, if i < j and A[i] A[j], then the pair (i,j) is called an inversion of A.How many inversions are there in the array A = {n,n-1...
2 votes
2 votes
1 answer
4
rsansiya111 asked Dec 8, 2021
833 views
Suppose we do merge sort with a three-way split: divide the array into 3 equal parts, sort each part and do a 3 way merge.What would the worst-case complexity of this ver...