DLet f(n) = n 2 . Is there anything wrong with the following proof by induction that f(n) = O(n)?

SHOW ALL STEPS FULL DETAIL

Basis: The case n = 1 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: f(n) = n^2 =

= (n 1)^2 + 2n 1

= f(n 1) + 2n 1 c(n 1) + 2n 1

= (c + 2)n c 1 < (c + 2)n.

Therefore by definition of the big O, f(n) = O(n).