Question: suppose we have a subroutine merge2 to merge two sorted...
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.