Determine Big O for the following recurrence relations using the Master Theorem if applicable, otherwise use Repeated Substitution. Show your work. Simplify the answer. a) T(n) = 1 T(n) = 9T(n/3) + n...

Determine Big O for the following recurrence relations using the Master Theorem if applicable, otherwise use Repeated Substitution. Show your work. Simplify the answer.

a) T(n) = 1
T(n) = 9T(n/3) + n

b) T(n) = 1
T(n) = 2T(n - 1) + 1

Master Theorem

when n=1 when n>1

when n=1 when n>1

For T(n) = A T(n/B) + O(nk) where A 3 1, B > 1