Oct 10, 2018

[HDGEM] 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(n3)+O(n)

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

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

S(0)=O(1)
S(k)=3S(k1)+O(3k)

Step 3: We solve the recurrence



--
Posted By Blogger to HDGEM at 3/06/2017 09:09:00 PM