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

Question

I'm taking a course in Discrete Mathematics this summer, and my book doesn't offer a very good explanation of Big-O notation. I understand that if $f(x)$ is $\mathcal O(g(x))$ it means that there exists some constant $C$ and some value $k$ (for $x$) where $C\cdot g(x)$ will be greater than $f(x)$. However, I don't understand how to prove this.

The book example gives the function $f(x) = x^2 + 2x + 1$ is $\mathcal O(x^2)$. My book states that "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 \le x^2 + 2x + 1 \le x^2 + 2x^2 + x^2 = 4x^2$."

By that example, I see that the constant $C$ is $4$ and $k$ is $1$. However, I don't understand at all why they just decided to throw $x^2$ everywhere and then sum the coefficients to get $4$ as the answer for $C$. Please help!!!

Answer 1

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

Answer 2

Hint

What's the relation between $n^2 + 2n + 3 =\mathcal O(n^2)$ and $\displaystyle\lim_{n\to\infty}\frac{n^2+2n+3}{n^2}$ ?

Answer 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

Answer 4

You want to look at all the terms in the expression and bound each of them by a multiple of the dominant term. Then add up the multiples of each term to get a bound for the whole expression.

In your case, the terms are $n^2$, $2n$, and $3$, and the dominant term is $n^2$.

So, you want to find $a$, $b$, and $c$ such that $n^2 \le a n^2$, $2n \le n^2$, and $3 \le c n^3$ for all $n > n_0$ for some $n_0$.

Obviously $a = 1$ works for all $n$.

If $2n \le b n^2$, then $2 \le b n$, and this is true for $b = 1$ for $n \ge 2$.

Note that big-oh (and little-oh) notation means the bound holds for all $large$ $enough$ $n$, so you do not need to worry about some initial values for which the bound is false.

Finally, $3 \le c n^2$ is true for $c = 3$ for all $n$.

Therefore, for $n \ge 2$, $n^2+2n+2 \le n^2+1n^2+3n^2 = 5n^2 $, so $n^2+2n+2 = O(n^2) $.

Note that (1) by choosing a larger $n$, we can get better values of $b$ and $c$, and (2) to prove a big-oh result, we don't need better values - $any$ values will do. However, if we are doing actual computations, we often want the best values (or, at least, pretty good values) for the coefficients of the smaller terms.

Answer 5

we have 2 cases for big-oh notation (1) take the highest coefficient as k. In this case compare all the terms along with their coefficients with leading term and replace the leading term in all other terms without coefficient then sum up the term to get a single term with highest coefficient and that coefficient is treated as c. in second case take the least coefficient as k which should be greater than x and compare all the term s with leading term without coefficients and then replace the leading term in all terms sum up the terms and get 1 term with highest coefficient that will b treated as c. let we have n^2 + 2(n) +3 according to first case highest coefficient is 2 and for 2>x and 2(n)x, k=1 now we find c. in this case 2<=n^2 , 3<=n^2 now replace leading term in other terms along with their coefficients we get n^2 + 2(n^2) + 3(n^2) = 6(n^2) so c=6 we don't have any restriction which case to use.

Answer 6

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.