For each of the following two recurrences, construct a recursion tree and use it to solve the recurrence. Your solution should include

a sketch of the tree

accounting of the depth, number of nodes, work per node, and work per level at each level of the tree

a summation giving the total work of the recurrence

a closed-form asymptotic solution to the recurrence

You may assume for simplicity that the input size n is a power of b, the denominator of the size in the recursive term, and that T(1) = d for some constant d.

1. T(n) = 3T(n/2) + n²

2. T(n) = 16T(n/4) + n²

Now, for each of the following recurrences, what (if any) asymptotic solution does the Master Method give? You should use the extended version of the Master Theorem (found on Wikipedia) that we referenced in studio. If this version of the Master Theorem gives no solution, say so in which case you do not need to solve the recurrence. Show your work: what are a and b, and what test did you do to determine which case, if any, you are in?

3. T(n) = 16T(n/2) + 3n⁴log²n

4. T(n) = T(n/3) + 4log n

5. T(n) = 4T(n/4) + (n/log n)

6. T(n) = 9T(n/4) + 2n^log₄9

7. T(n) = 11T(n/3) + n²

8. T(n) = 999T(n/10) + 2n³

9. T(n) = 7T(n/2) + n³ (log n)log(log n)