1. [10 marks] 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) Tn) 1 when n=1 8T(n/4) + n2 when n>1 b) T(n) T(n) 1 when n=1 2T(n - 1) +1 when n>1 Master Theorem For T(n) = A T(n/B) + O(nk) where A 21, B > 1 T(n) = O(nloge 4), A>Bk O(n* log n), A=B On*), A