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 8T(n/4) +n? when n=1 when n>1 b) T(n) Tn) 1 when n=1 2T(n-1) +1 when n>1 Master Theorem For T(n) = A T(n/B) + O(n) where A > 1,B> 1 T(n)= O(nlogy), A > Bk O(nk log n), A = }} On), A