Consider an algorithm sort(A) that takes as input an array A of integers. The algorithm works by calling aux(0, n, A) where n is the length of A and where aux(lo, hi, A) is a recursive algorithm. The arguments lo and hi of aux delimit the portion of the array A that aux sorts, namely A[lo], A[lo + 1], . . . , A[hi 1].

aux(lo, hi, A) works as follows:

1. If hi lo is 0 or 1, return. Otherwise go to the next step.

2. If hi lo is 2, put A[lo] and A[hi 1] in order (swap if needed) then return. Otherwise go to the next step.

3. Divide the array portion between lo and hi into three (approximately) equal parts. Call insertionsort to order the middle third, then recursively call aux for the lower third, and finally recursively call aux for the upper third.

4. Merge all three sorted parts.

a. Let T(n) be the worst-case running time for sort on an array of length n (assume that n is an exact power of 3). Write a recurrence relation for T(n). On the right side of the recurrence relation do not include the terms of the form c np where p 0, except for the term of highest degree. Explain your answer briefly.

b. Analyze the running time of the algorithm. Prove this.