Answer:
Since we extract n elements in total, the algorithm for the running time for K sorted list is O (n log k+ k) = O (n log k)
Step-by-step explanation:
To understand better how we arrived at the aforementioned algorithm, we take it step by step
a, Construct a min-heap of the minimum elements from each of "k" lists.
The creation of this min-heap will cost O (k) time.
b) Next we run delete Minimum and move the minimum element to the output array.
Each extraction takes O (log k) time.
c) Then insert into the heap the next element from the list from which the element was extracted.
Now, we note that since we extract n elements in total, the running time is
O (n log k+ k) = O (n log k).
So we can conclude that :
Since we extract n elements in total, the algorithm for the running time for K sorted list is O (n log k+ k) = O (n log k)
