Suppose we have a subroutine merge2 to merge two sorted arrays in linear time ((kn)). The purpose is to design a divide and conquer algorithm (Alg2) to merge k sorted arrays using merge2 recursively. a) Write a pseudocode for Alg2. (Hint: Assume that the input is given in a (k x n) array with the rows and columns sorted in ascending order)

b) Write the running time of Alg2 as a recurence relation. T(k) =?

c) Construct a recursion tree with log k levels and (kn) work per level to represent the recurance relation obtained in part (b).

d) Since k is a constant, is Alg2 asymptotically faster than an algorithm with running time (n log n)? why?

Please give a detailed answer for all the parts as I'm trying to understand how to solve these problems.

Transcribed image text