The purpose of this question is to analyze, using the recursion tree method, an algorithm whose time complexity T(n) satisfies the following recurrence: T(1) = c1, and if n > 1 then T(n) = 6T(n/3) + c2n^2 where c1 and c2 are constants. We assume that n = 3^q for some integer q

1. Derive an exact expression (i.e., not in asymptotic notation), as a function of n, for the height of the recursion tree (recall that the height of a tree is the largest number of parent-to-child links one goes through from the root to the deepest leaf).

2. Write down an expression for the work associated with level i of the recursion tree (e.g., for level 0, which is the root, it is c2n^2 ).

3. Derive the asymptotic growth rate of the solution for T(n) (i.e., its rate of growth as a function of n using asymptotic notation, not its exact value).

Question 2. (15 points) The purpose of this question is to analyze, using the recursion tree method, an algorithm whose time complexity T(n) satisfies the following recurrence: T(1) = ci, and if n > 1 then T(n) = 6T(n/3) + cand where ci and ca are constants. We assume that n = 39 for some integer q. 1. Derive an exact expression (i.e., not in asymptotic notation), as a function of n, for the height of the recursion tree (recall that the height of a tree is the largest number of parent-to-child links one goes through from the root to the deepest leaf). 2. Write down an expression for the work associated with level i of the recursion tree (e.g., for level 0, which is the root, it is c2n). 3. Derive the "asymptotic growth rate" of the solution for T(n) i.e., its rate of growth as a function of n using @ asymptotic notation, not its exact value)