The Master Theorem Use the Master Theorem (as stated in the lecture slides) to find a simple Big-Theta expression for the recurrences below. Clearly indicate which case of the Theorem applies and what the values a, b, c and g(n) are for each recurrence. In the event that case 3 of the theorem applies, remember to clearly state whether the extra condition ag(n/b) 1 (b) (Assume n is a power of 3) T(n) = {17 if n = 1 2T(n/3) + n if n > 1 (c) Assume n is a power of 3) T(n) = {17 if n = 1 9T(n/3) + n if n > 1