2

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.

tenkii
  • 137
  • Do you want to know how the witness is found in general ? – Peter Nov 25 '15 at 13:37
  • Can you tell me how to find it for this example first? – tenkii Nov 25 '15 at 13:39
  • Rather than the described method, I would argue that $\lim_{x\rightarrow \infty} x^2-2x-1=\infty$ , so $2x^2-(x^2+2x+1)>0$ holds for every $x>m$ for some suitable number $m$, therefore $2x^2>x^2+2x+1$ for $x>m$ and therefore $2x^2$ is a witness. This procedure has the advantage that it can be applied to every polynomial. And this way it is easy to see that for a polynomial $p$ with degree $d$ we have $p(x)=O(x^d)$ – Peter Nov 25 '15 at 13:43
  • The described method is easy to verify, but it is hard to have the idea, so maybe you prefer my approach. – Peter Nov 25 '15 at 13:46

1 Answers1

3

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$.

Mankind
  • 13,170
  • Hi. Thanks for your reply. I am trying to make sense of it. How do you note that "$x≤x^2$ and $1≤x^2$ for all $x≥1$."

    How are these derived (without a graph)?

     – tenkii Nov 25 '15 at 14:43
  • @tenkii No problem. From the inequality $1\leq x$, you can multiply both sides by $x$ to get $x\leq x^2$. This is the first part. Since $1\leq x$, and $x\leq x^2$, we also get $1\leq x^2$. This is the second part. Let me know, if this makes sense. – Mankind Nov 25 '15 at 15:14
  • @HowIDoMath The multiplying parts makes some sense. But how do we come up with the first equality that $1≤x$? [Side note: I see that this first equality is what we base everything on and the answer should follow through. And this is our k right? If so, how can we pick it correctly] – tenkii Nov 25 '15 at 17:19
  • 1
    @tenkii You are correct that the $1$ in the expression $1\leq x$ is our $k$. How does one come up with this? There's several answers: Knowledge, experience, trial-and-error, ... where the most important part is definitely experience. One has to train. I can tell you that whenever $1\leq x$, and if $m\leq n$, then we always have $x^m\leq x^n$. This means that if you come across polynomials in future problems, then you know when one is larger than the other, and at what value ($x=1$) it happens. For instance, $x^3+3x^2+2x+5\leq x^3+3x^3+2x^3+5x^3 = 11x^3$ as long as $x\geq 1$. Here $k=1$ again. – Mankind Nov 25 '15 at 21:39