GATE 2005
March 12, 2025GATE 2005
March 12, 2025GATE 2005
|
Question 39
|
Suppose there are ⌈log n⌉ sorted lists of ⌊n/log n⌋ elements each. The time complexity of producing a sorted list of all these elements is: (Hint: Use a heap data structure)
|
O(nlog log n)
|
|
|
θ(nlog n)
|
|
|
Ω(nlog n)
|
|
|
Ω(n3/2)
|
Question 39 Explanation:
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)
P = log n
Q = n/log n
∴ Putting values we get,
O(n log log n)
Correct Answer: A
Question 39 Explanation:
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)
P = log n
Q = n/log n
∴ Putting values we get,
O(n log log n)