Published on

The Algorithm Design Manual (3rd) Exercise Solution 'E4-29'

Table of Contents

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 4-29

Question

Suppose you are given k sorted arrays, each with n elements, and you want to combine them into a single sorted array of kn elements. One approach is to use the merge subroutine repeatedly, merging the first two arrays, then merging the result with the third array, then with the fourth array, and so on until you merge in the kth and final input array. What is the running time?

Solution

The number of merging is k−1k-1. Let lil_i be the number of total elements of two array involving the i-th merge.
In the second half of merging (when i≥k−12i \ge \frac{k-1}{2}), lil_i is greater than or equal to the half of kn.

So, the following binding constraint on the running time holds:

k−12∗O(kn2)<Running-time<(k−1)∗O(kn)  ⟹  Running-time=Θ(k2n)\begin{align} &\frac{k-1}{2}*O(\frac{kn}{2})<\text{Running-time}<(k-1)*O(kn) \\ \implies &\text{Running-time}=\Theta(k^2n) \end{align}