Algorithms: Design and Analysis, Part 1 - Problem Set 1 - Question 1

Problem:

3-way-Merge Sort : Suppose that instead of dividing in half at each step of Merge Sort, you divide into thirds, sort each third, and finally combine all of them using a three-way merge subroutine. What is the overall asymptotic running time of this algorithm? (Hint: Note that the merge step can still be implemented in $O(n)$ time.)

Solution:

Step 1: Write down the recurrence

$T(1) = O(1)$
$T(n) = 3T(\frac{n}{3}) + O(n)$

Step 2: Assuming $n = 3^k$, simplify the recurrence

Let $S(k) = T(3^k)$, therefore, we have

$S(0) = O(1)$
$S(k) = 3S(k - 1) + O(3^k)$

Step 3: We solve the recurrence

$\begin{eqnarray*} & & S(k) \\ &=& 3S(k - 1) + O(3^k) \\ &=& 3(3(S(k - 2) + O(3^{k - 1})) + O(3^k) \\ &=& 3^2S(k - 2) + O(3^k) + O(3^k) \\ &=& 3^2S(k - 2) + 2O(3^k) \\ &=& 3^kS(k - k) + kO(3^k) \\ &=& 3^kO(1) + kO(3^k) \\ &=& O(k3^k) \\ &=& O(n \log n) \\ \end{eqnarray*}$