Sam Smartypants likes how splitting the problem up into halves in merge sort reduces the sorting problem from O(n² ) 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.