2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The difficulty with using a limit like this in general is that it doesn't imply that $2n^2 + n + 1\leq Cn^2$ for $n$ large enough--at least not taking $C=2$ since $2n^2 + n + 1 > 2n^2$. What you want to argue, is that this limit being finite means that everything other than the $2n^2$ factor out front really don't matter... they are comparatively small (to $n^2$). This usually means that the inequality (like $n\leq n^2$) is fairly trivial. $\endgroup$ – TravisJ Mar 18 '15 at 20:23
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The fact that $\{n\in \mathbb{N}: n\leq N\}$ is finite is not necessary. You only need to show that $n^2+n+1\leq 3n^2$ for $n$ large enough (i.e. larger than $N$). $\endgroup$ – TravisJ Mar 18 '15 at 20:27
  • $\begingroup$ @TravisJ You're right. Thank you for noticing it. $\endgroup$ – mfl Mar 18 '15 at 20:33
  • 1
    $\begingroup$ I think this just about explains it, however there is still something that still looks like it was magic, and not with the limit part but instead with the "normal" proof, and that is the $2n^2 + n^2 + n^2$, I mean where does it come from and why is it valid to do that? I keep seeing that with Big O but I don't really understand it. I know it can be used to do this: $n^2(2+1+1) = 4n^2$, but how does one go from the normal expression to that? $\endgroup$ – Argus Mar 19 '15 at 1:30
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I interpreted it to mean: justify why one could compute such a limit in general and have it work. Not: justify the computation of the limit (i.e. that the result is 2, not 0 or $\infty$. $\endgroup$ – TravisJ Mar 18 '15 at 20:19
  • $\begingroup$ I see, then you would justify by noting that as long as the ratio is finite, at the limit that is, then the bound has to be greater than the function f(x). $\endgroup$ – Zach466920 Mar 18 '15 at 20:23
  • 1
    $\begingroup$ That is pretty correct. See the explanation of mfl (another answer) for details as to how to make that argument. $\endgroup$ – TravisJ Mar 18 '15 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.