Suppose there are logn sorted lists of n/logn elements each. The time complexity of producing a sorted list of all these elements is (use heap data structure)
A. O(n log logn)
B. θ(n logn)
C. Ω(n logn)
D. Ω(n3/2)
Answer:A
Suppose there are logn sorted lists of n/logn elements each. The time complexity of producing a sorted list of all these elements is (use heap data structure)
A. O(n log logn) B. θ(n logn) C. Ω(n logn) D. Ω(n3/2)
Explanation: We can merge m arrays of each size n in in O(MN*LogN) time using Min Heap.