Need help understanding a derivation of "witnesses" for a Landau bound So here's an excerpt from Foundations of Computer Science by Alfred Aho and Jeffrey Ullman[1]. I've also found basically the same material in a few other places, and also in my discrete math textbook, but this is clearest one I've seen:


  Example 3.2. Suppose we have a program whose running time is $T(0) = 1$, $T(1) = 4$, $T(2) = 9$, and in general $T(n) = (n + 1)^2$. We can say that $T(n)$ is $O(n^2)$, or that $T(n)$ is quadratic, because we can choose witnesses $n_{0} = 1$ and $c = 4$. We then need to prove that $(n + 1)^2 \leq 4n^2$, provided $n \leq 1$. In proof, expand $(n + 1)^2$ as $n^2 + 2n + 1$. As long as $n \leq 1$, we know that $n \leq n^2$ and $1 \leq n^2$. Thus $n^2 + 2n + 1 \leq n^2 + 2n^2 + n^2 = 4n^2$.


Even so, I get lost where it says:

$$
n^2 + 2n + 1 \leq n^2 + 2n^2 + n^2
$$

I get that it's true, but it seems arbitrary. How/why did the expression get modified on the right side of the $\leq$ like it did? Couldn't they also have done this?

$$
n^2 + 2n + 1 \leq 4n^2 + 0 + 0
$$

Specifically, what rule did they apply to transform the expression $n^2 + 2n + 1$ into $n^2 + 2n^2 + n^2$?




http://infolab.stanford.edu/~ullman/focs.html
They want to end up with ​ constant * n2 ​ on the very-right.

They applied "make each term a constant times n2".