# taking limits and asymptotic analysis

I saw a some proofs like this:

To prove $N^2+3N=O(N^3)$

$$\lim_{N\to\infty} \frac{N^2+3N}{N^3}=0$$

then $N^2+3N$ is $O(N^3)$ and if the result is infinity left hand side is Big Omega of right hand side, and There are some situations limits not exits...

I was told this is by some theorem..I can just use it but I would like to know some details and reasoning behind this.

I wonder if some one can give me a link or tell me which aspect to search

thanks for any help!

-

Now suppose

$$\lim_{n\to\infty}\frac{f(n)}{g(n)}=0.$$

By the definition of a limit, for any $\epsilon>0$, there is an $m$ such that $|f(n)/g(n)-0|<\epsilon$ for $n\ge m$. So this means that $f(n)<\epsilon\, g(n)$ for all $n\ge m$, which is fulfills the existential definition for $f=\mathcal{O}(g)$.

Likewise, suppose

$$\lim_{n\to\infty}\frac{f(n)}{g(n)}=+\infty.$$

By the definition of a limit "equaling" positive infinity, for any positive $L>0$, we know there is an integer $m$ such that $f(n)/g(n)>L$ for all $n\ge m$. Hence $f(n)>Lg(n)$ for all $n\ge m$, which fulfills the existential part of the definition for $f=\Omega(g)$.

Here we assume $f$ and $g$ are positive-valued functions.

-