1. Engineering
  2. Computer Science
  3. suppose we have a subroutine merge2 to merge two sorted...

Question: suppose we have a subroutine merge2 to merge two sorted...

Question details

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 \small \Theta(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
\small \Theta(n log n)? why?

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

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution