Please give explanation why you chose your answer so I can compare with answer I
ID: 3802697 • Letter: P
Question
Please give explanation why you chose your answer so I can compare with answer I chose to see difference if there are any. Thanks will give good feedback
Question 3 1 pts Consider the same problem as above: Suppose we have k sorted lists, each with exactly n elements, that we would like to merge (so we end up with a sorted list of length kn). This time, we do a k way merge, as follows: we maintain a binary min-heap of size k, containing the smallest elements from each of the k input lists. Now, we proceed for kn iterations in each iteration, we extract the minimum element from the heap and add it to the output array. Then we delete the corresponding element from the input list where it came from, and insert the new smallest element from that list to the heap. What is the overall running time of this algorithm (in big-Theta notation k2n. 2 kn log (k) kn. k2n.Explanation / Answer
Solution to Q.3) knlog(k)
Reason : Finding minimum from the heap has O(log k) time complexity. This process needs to be repeated for a total of n*k times. So, the final time complexity becomes (n*k log(k)).
Solution to Q.4) Insert : O(n), Extract-Max: O(1), Change-Priority: O(n)
Reason : Inserting an element in priority queue using sorted linked list will take O(n) time, as we need to find the location for the new element in sorted linked list.
Extracting max takes only O(1) time as it will return the last element of linked list (highest priority is at the end).
To change priority of existing element will require finding and replecing its old priority with the new priority so it will take O(n) time.