Need help with the following questions please.

9. (5) Let f(n)n. Is there anything wrong with the following proof by induction that f(n) O(n)? Basis: The case n1 is trivially satisfied since f (1) 1 is a constant Induction Hypothesis: Assume that f(n -1) c(n-1) for some constant c>0 Induction step: = (n-1 )2 + 2n-1 - f(n - 1) +2n - 1 S c(n-1) +2n -1 - (c+ 2)n -c-1 f(n) = Therefore by definition of the big O, f(n) O(n) 10. (10) Solve the following recurrence with three different methods: iteration, recursion tree, and substitution. Can we use the master method for this recurrence? Why or why not? Show your work. tn)tn/2) +logn t(1) constant