NPTEL Assignment Question

Question

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)

Answer 1

Option A should be TRUE

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

Comments

@[jiren] Nice soln. Just that in point 2, it will be among all 'k' elements. And 3rd point will be logk.

---

@Abhrajyoti00

Thnx for the correction

That log n thing is a typo it must be log k

in point 2 i was referring for only first extract min operation  as this will give Min element among all n elements

---

overall complexity for first pass of picking k elements is O(k + logk + logk)

afterwards we pick single element, O(logk + logk) for next n-k elements bcz after first pass we have to insert only single element in min heap from that subarray from which we picked a minimum in  just previous pass.

so Total complexity will be 1 * O(k + logk + logk)  + (n-k) * O(logk + logk) = O(2 (n-k) logk)

 =  O(nlogk) , k<=n

---

@Genius

How is ur solution different than the solution that i wrote ??

im not getting why u commented the exact procedure

any specific reason ??

---

only one difference you wrote overall complexity for single element but i.e. for first k element.

Answer 2

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

 

 

Comments

Hi

From the given options you have to pick the most optimal answer

n*logn will definitely work but its not an optimised solution

in my opinion n*log k should be the answer

Answer 3

T(n) = O(nlogk)

option A

Comments

Hi

this is not the correct way to answer a question bro

simply stating the answer is not a good practise

Atleast u should have written the outline of the solution