Please number the question you are answering and if possible keep the solution as simple as possible. Thank you! Please use either expansion or tree method as asked in the question.

Give asymptotic upper bounds for T(n) satisfying the following recurrences. Make your bounds as tight as possible. Note that "tight upper bound means the best possible Big-Oh answer. So, T(n) = O(n") would not be considered a fully correct answer if T(n) = O(n^) as well. You must prove your results from scratch using either the expansion or tree method shown in class. Show all of your work. For (a) you may assume that n is a power of 4; for (b) you may assume that it is a power of 3. (a) T(1) = 1; T(n) = 6T (n/4) + n2 for n > 1. (b) T(1) = 1; T(n) = 9T (n/3) +n for n > 1