Suppose you are writing an algorithm to merge k sorted arrays of size n into a single sorted array of size kn. You write an algorithm to do so that (1) makes a recursive call to merge the first k/2 arrays, (2) makes another recursive call to merge the remaining k/2 arrays, then (3) merges the results from the calls in (1) and (2). Suppose the cost of merging two sorted arrays of sizes a and b is a+b. Suppose you are sitting at the root of the recursion tree, where the last two arrays of size kn/2 will be merged. What will be the total cost of the algorithm at this level of the tree? Give your answer as an expression in terms of n and k (in simplest form).

sol18:

At the root of the recursion tree, we have two arrays of size kn/2 that need to be merged. Each of these arrays can be divided into k/2 arrays of size n/2. We can merge these smaller arrays in pairs to form k/4 arrays of size n. We can then merge these pairs of size n to form k/8 arrays of size 2n. Continuing this process, we eventually obtain two sorted arrays of size kn/2 that need to be merged. The total cost of the algorithm at the root of the recursion tree can be expressed as:

k/2*(n/2 + n/2) + k/4*(n + n) + k/8*(2n + 2n) + ... + 2*(kn/2 + kn/2)

Simplifying each term in the sum, we get:

kn/2 + kn/2 + kn/2 + kn/2 + ... + kn/2

There are k/2 terms in the sum, so we can simplify it to:

k/2 * kn/2 = k^2*n/4

Therefore, the total cost of the algorithm at the root of the recursion tree is k^2*n/4.