Assume that you are given an algorithm named Merge that can merge two sorted int
ID: 3883200 • Letter: A
Question
Assume that you are given an algorithm named Merge that can merge two sorted integer arrays of size n and m to generate a new sorted array of size n + M in O(m + n) time. Your task is to use Merge merge k sorted integer arrays each containing n elements, and output a single sorted array. Consider the following algorithm for this task. Let A_1,A_2,..,A_k be the input arrays. A = empty array. For i in range [1...k] A = Merge (A_i, A): Return A: Derive the worst-case asymptotic time complexity of the above algorithm.Explanation / Answer
If we combine two sorted arrays with size n and m we combine arrays by taking two pointers at start of the arrays and we check the values at those pointers and insert the small value in the result array and move the array pointer by one position in which the value is selected and continue until we reach the end of one array then the other array is inserted directly in to the array . In Worst case we make at maximum of n+m comparisions. So the time complexity is O(n+m).
First there are 0 elements in A array. Firstly we add n elements in first array (A1) for that the time complexity is O(0+n) i.e., O(n). Next by adding second array , the size of A is n and the size of next Array A2 is of size n it takes time of O(n+n) i.e., O(2*n). Similarly by adding k arrays of size n we get time complexity of O(k*n).