Proving that $2n^2 + n + 1 = O(n^2)$ and big O proofs in general

Question

Alright so here's the thing, I'm in a class in Computer Science called Algorithm Analysis and it is required for me to learn Big O, Big Omega, etc. While I sort of understand what this is for, I still don't don't quite get how to prove that an function belongs to $O(n)$ or $O(n^2)$ or really any other function. I know this is used to check the way an algorithm behaves.

For example, I found out this:

$$\lim _{n\to \infty }\left(\frac{2n^2+n+1}{n^2}\right) = 2$$

And because it equals 2 according to what I've found on the internet, then $f(n)$ and $g(n)$ have an equal growth, therefore $f(n)$ is part of $O(n^2)$.

Now here's my issue, I told my professor about this, but he told me that if I want it to prove Big O with limits, then I needed to justify that operation. I don't know how to do that, or what he meant exactly, maybe he wanted to know why the function belongs to that particular Big O, if someone could explain the "why of things" with this. Aside from that my professor proves Big O and Big Omega through a constructive proof, which I really do not understand, aside from knowing that you need to proof the existence of two constants that make $f(n) \le O(n^2)$. However that's about it, that's as much as I know.

Answer 1

You can show that $2n^2+n+1=O(n^2)$ directly in an easy way. Since

$$2n^2+n+1\le 2n^2+n^2+n^2=4n^2$$ you have the desired result.

On the other hand, sometimes find an explicit bound can be not so easy. The idea with limits works as follows. Since

$$\lim _{n\to \infty }\left(\frac{2n^2+n+1}{n^2}\right) = 2,$$

by definition of limit, for any $\epsilon>0$ there exists $N\in\mathbb{N}$ such that

$$n\ge N \implies \left|\frac{2n^2+n+1}{n^2}-2\right|<\epsilon.$$ That is,

$$n\ge N \implies 2n^2+n+1<(2+\epsilon)n^2.$$ Now, consider a particular $\epsilon,$ say $\epsilon=1.$ Then,

$$n\ge N \implies 2n^2+n+1<3n^2.$$

Thus we have shown that $2n^2+n+1=O(n^2).$

Answer 2

Basically, you are identifying the part of the function that grows the fastest. The easiest way to prove this particular function is $O(n^2)$ is to first notice that $n\leq n^2$ and $1\leq n^2$ (both for $n\geq 1$). Then you can simply say:

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

So, $2n^2 + n + 1 = O(n^2)$. Keep in mind what the $O$ notation means... if $n$ is large enough (say larger than 1) then there is a constant (in this case 4 is big enough constant) so that $f(n)\leq 4n^2$.

Answer 3

I think he means justify the limit. You can also prove $f(x)$ is part of $O(n^2)$ by proving f(x) is bounded above by some $n^p$ for all x after a given interval. Also remember that your function could be bounded by a log or even an exponential function