PLEASE URGENT

Exam 1 Ari Mermelstein March 12. 2019 1 Induction - 10 points Prove that (A-1)=nR 2 O' notation-20 points -1 Is f(n) E 0(g(n)), f(n)-(g(n)), or f(n)s eg(n))? Prove your anner using the limit definition or the algebrale definition. Show all work g(n)6n gin) - nm g(n) = log n + 1. g(n)- n 2. f(n)n+ n log n 3. f(n)- (log n)2 5f(n) = 2" 3 Master Theorem- 20 points Use the Master Theorem to solve the following recurrences: 1 . T(n) = 5T(+69(n) 2. T(n) 47(9) + (n3) 5. Ton) 2713) + (n)