Algorithms: Design and Analysis, Part 1 - Exam Question 18

Problem:

Suppose you are given $k$ sorted arrays, each with $n$ elements, and you want to combine them into a single array of kn elements. Consider the following approach. Divide the $k$ arrays into $k/2$ pairs of arrays, and use the Merge subroutine taught in the MergeSort lectures to combine each pair. Now you are left with $k/2$ sorted arrays, each with $2n$ elements. Repeat this approach until you have a single sorted array with kn elements. What is the running time of this procedure, as a function of $k$ and $n$?

Solution:

The first iteration deal with $\frac{k}{2}$ array of length $n$, so it takes $\theta(nk)$ time.
The second iteration deal with $\frac{k}{4}$ array of length $2n$, so it also takes $\theta(nk)$ time.

Therefore the overall execution time is really just $\theta(nk\log k)$ time.

This is simply and I should have got this correct, I made a careless mistake here, sigh.