I am trying to follow this example but I am stumped by where numbers are coming from:
Show that $f (x) = x^2 + 2x + 1 $ is $O(x^2). $
The solution is as follows:
We observe that we can readily estimate the size of $f (x$) when $x > 1$ because $x < x^2$ and $1 < x^2$ when $x > 1$. It follows that $$0 ≤ x^2 + 2x + 1 ≤ x^2 + 2x^2 + x^2 =4x^2$$ whenever $x > 1$. Consequently, we can take $C = 4$ and $k = 1$ as witnesses to show that $f (x)$ is $O(x^2)$. That is, $f (x) = x^2 + 2x + 1 < 4x^2$ whenever $x > 1$.
Can someone explain where the numbers are coming from in the equality? I tried to ask someone but I still did't understand. I would very much appreicate a "dumbed down" explanation.
The important thing to note is that $x\leq x^2$ and $1\leq x^2$ for all $x\geq 1$.
You can convince yourself of this by plotting $x$, $x^2$, and $1$ on the same graph, as I've done here. You see that $x^2$ is the largest whenever $x>1$.
So suppose we have an $x\geq 1$. Then $x\leq x^2$, and multiplying both sides by $2$, we also have $2x\leq 2x^2$.
This is all important, because your function $f(x)=x^2+2x+1$ contains three terms, and we are interested in bounding each of them. A good candidate for a bounding function in a polynomial is always the highest degree term, which in this case is $x^2$. Indeed, we have by the above that whenever $x\geq 1$, then
$$f(x)=x^2+2x+1\leq x^2+2x^2+x^2 = 4x^2.$$
Here I just used that $x^2\leq x^2$ (well, they are really equal), that $2x\leq 2x^2$ and that $1\leq x^2$.
This shows that $f(x)$ is bounded by $4x^2$, whenever $x\geq 1$, or in other words, that $f(x)$ is $O(x^2)$ with witnesses $C=4$ and $k=1$.