1
$\begingroup$

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!

1 Answers 1

2

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.