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*} $