Big-O Notation - Prove that $n^2 + 2n + 3$ is $\mathcal O(n^2)$

Solution 1:

Wow, this is a pretty old thread, but hopefully you were able to figure it out. For anyone else who comes across this in the future, I hope this helps:

If $n^2 + 2n + 3$ is $O(n^2)$, then we must show that for all $n \geq k$, some constant multiple of the leading term of our function ($n^2$), stripped of any constants, will always overtake the function. That is:

For $n \geq k$, we can say there exists a constant $c$ such that $n^2 + 2n + 3 \leq c*n^2$. And our task is twofold: first specify a value for $k$, and then find the value of $c$.

Now, we can pick any $k$ we like, and it's usually easiest to pick $k=1$, so let's go ahead and do so:

$n \geq k = 1$ i.e. $n \geq 1$

Now, our goal is to show that for some constant--any constant--$c$, the right hand side will always overtake the left hand side. Consider the pesky $2n$ on the left side:

We know that $n \geq 1$, so it follows that $n^2 \geq n$ (by multiplying both sides by $n$, which is not negative, and hence the $\geq$ sign remains unchaged). We can sort of form a chain conclusion by remembering that $n \geq 1$, so we can also conclude that:

$n^2 \geq n \geq 1$

$2n^2 \geq 2n \geq 2$

By the same token, moving on to the troublesome $+3$ term, note that if $n \geq 1$, then:

$3n^2 \geq 3n \geq 3$.

And by the very nature of greater than or equal to, $n^2 \geq n^2$.

So we can form the following inequality:

$n^2 + 2n + 3 \leq n^2 + 2n^2 + 3n^2$

Where each term of the right side is greater than or equal to the corresponding terms on the left, such that the sum of the right terms is greater or equal to the sum of the left terms:

$n^2 + 2n + 3 \leq 6n^2$

So voila, we let $c = 6$ and $n \geq 1$, and we've therefore shown that this function is of complexity $O(n^2)$.

Just to check our work, we can plug in integer values for $n$ starting with $1$:

$1^2 + 2 + 3 = 6 \leq 6(1^2)$
$2^2 + 2(2) + 3 = 11 \leq 6(2^2) = 24$

And so on.

Solution 2:

Basically: they did it because it was easy!

The real idea of Big-O notation is to find whatever term gives you the major contribution -- in this case, we know that $x^2$ is much larger than $x$ when $x$ is large -- and bound by it.

They could just as easily have said that when $x\geq 2$, we have $2x\leq x^2$ and $1\leq x^2$, and made the constant 3. The specifics can vary almost as much as you like... and at the end, the value of $C$ is actually of no consequence. But it won't change the fact that when push comes to shove, the rate of growth of this function is on the order of $x^2$.

Solution 3:

Here's an equivalent definition which, to me, is much clearer:

We state that $f(x)=\mathcal O(g)$ if there's some constant $C$ such that for a sufficiently large $x$: $$ \left|\frac{f(x)}{g(x)}\right|<C $$ The only difference here is that we've divided both sides by $g$. So, in this case, we'd like to find a $C$ so that for a big enough $x$, $$ \left|\frac{x^2+2x+1}{x^2}\right|<C $$ You might know from calculus that the limit of this fraction as $x\to\infty$ is $1$, which means that this fraction will eventually go below any $C>1$. Since any such $C$ will do for our proof though, it is convenient to make the argument that for $x>1$, $$ \left|\frac{x^2+2x+1}{x^2}\right|< \left|\frac{x^2+2x^2+x^2}{x^2}\right|=4 $$ which means that $C=4$ is a suitable constant. Note that there's nothing special here about $4$, proving $f(x)=\mathcal O(g)$ just requires we find some $C$ that works. We could have made the argument that for $x>1/2$: $$ \left|\frac{x^2+2x+1}{x^2}\right|< \left|\frac{x^2+2(2x^2)+4x^2}{x^2}\right|=9 $$ And we'd have been able to make the same conclusion