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) = 2T(n/2) + 8T(n/4) + c2n^2 where c1 and c2 are constants. We assume that n = 4^q for some integer q.

1. Derive an expression, as a function of n, for the height h of the recursion tree.

2. Derive an expression, as a function of n, for the depth of the least-depth leaf in the recursion tree (i.e., leaf that is closest to the root). Also write down as a function of h. 3. Write down an expression for the work associated with level i of the recursion tree for i .

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

Question 3. (20 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) = 2T (n/2) + 8T(n/4) + c2n2 where ci and ca are constants. We assume that n = 49 for some integer q. 1. Derive an expression, as a function of n, for the height h of the recursion tree. 2. Derive an expression, as a function of n, for the depth l of the least-depth leaf in the recursion tree (i.e., leaf that is closest to the root). Also write down l as a function of h. 3. Write down an expression for the work associated with level i of the recursion tree for i