1. (5 miarks) Is 10n6 + 4n5 + 6m" + 2n3 + rt2 + 7n + 10 E o(r')? Prove? 2. (5 marks) Is nte o(10n + 4ns + 67,1 + 2n" + + 7n + 10)? Prove? 3, (5 marks) Is 32n-0(3")? Why? 4, (10 marks) Using the definitions of O and , show that (a) n3 + 3100',' E (724) (b) 10n6 + 4ns + 6n4 + 2n3 + n2 + 7n + 10 E (n6) 5, (15 marks) Solve the following recurrence relations and give a bound for each of thern (you do not need to show/prove how the bound is obtained): (a) T(n) = T(n-1) + 2n (b) T(n) 2T(n-1)+2 (c) T(n) = 2T(n/2) + 2n (assume T(0)0) (assume T(0-0) (assume T(1-1)