Sam Smartypants likes how splitting the problem up into halves in merge sort reduces the sorting problem from O(n2 ) to O(n lg n).
He decides that splitting the array into thirds will make things even better. That is, he decides to make a recursive call on each third of the array and then merge them.
(a) Assuming that n is a power of three, that T(1) = 1, and that the running time of the merge step is exactly n, give a recurrence for the running time of Sam's algorithm.
(b) Find the solution to the recurrence in big-Oh notation and prove it using the substitution method.