Asymptotic Notations in Limits Can the asymptotic notations, like Big O, be defined using limits?
example: $\lim_\limits{x\to\infty} (f(n)/g(n))=c$ for defining $f(n)=O(g(n))$
If not, why??
 A: If $g(n)$ is nonzero from some point on, then saying $f(n)=O(g(n))$ is the same as saying that $\frac{f(n)}{g(n)}$ is bounded for sufficiently large $n$. (And as Gina points out, this is the same as the condition for the limsup of the fraction to exist).
However, for small-o notation limits do come into play: $f(n)=o(g(n))$ exactly if $\lim\frac{f(n)}{g(n)}=0$.
A: It is very common for algorithm to run extremely fast in some case, and very slow on some other case, and that continued to infinity (integer factoring for example). Let's say the true amount of time take by an algorithm is $f(n)=\phi(n)$ and we want to use $g(n)=n$ to gauge its asymptotic time. Then $\frac{f(n)}{g(n)}\approx 1$ whenever $n$ is prime, and $\frac{f(n)}{g(n)}\approx\frac{1}{2}$ whenever $n$ is a power of $2$. Since there are arbitrarily large prime and power of 2, the sequence $\frac{f(n)}{g(n)}$ oscillate between $\frac{1}{2}$ and $1$. Hence $\lim\limits_{n\rightarrow\infty}\frac{f(n)}{g(n)}$ does not exist. However, it is still true that $f(n)\in O(g(n))$ because for all $n>1$ then $|f(n)|<|g(n)|$.
If you use $\limsup$ instead, this can make sense. While $\lim\limits_{n\rightarrow\infty}\frac{f(n)}{g(n)}$ does not exist, $\limsup\limits_{n\rightarrow\infty}\frac{f(n)}{g(n)}$ exist and is $1$. So we can define $f(n)\in O(g(n))$ to mean $\limsup\limits_{n\rightarrow\infty}\frac{|f(n)|}{|g(n)|}<\infty$. Of course for other asymptotic notation you might need $\liminf$ instead, or both.
