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)