Solve the following recurrence relations. Show your work, and state which case of the Master Theorem applies, and why.

1) T(n) = 2T(n/2) + n3

2) T(n) = T(9n/10) + n

3) T(n) = 16T(n/4) + n2

4) T(n) = 7T(n/3) + n2

5) T(n) = 7T(n/2) + n2

6) T(n) = 2T(n/4) + n

7)T(n) = 3T(n/2) + n lg n

8) T(n) = 4T(n/2) + n2 n