Substitution

How to prove by substitution:

1. Hypothesize big O of T(n).
2. Verify via induction using definition of big O.
3. Solve for constants $c$ and $n_0$.

Proof by induction

Assume $T(n)\le cn$ for $\forall n\le k-1$
Find $n_0$ and $c$ for $n=k$.