# Big O - Equivalence: “Standard” definition vs Limit definition

This question is related to: Landau Notation, Definitions: Limits vs. Cormen's.

Consider functions $f, \ g : N \rightarrow R^{\geq0}$.

For small-$o$, the definition: $$f(n)\in o(g(n)) \iff \forall c>0,\exists n_0>0, \forall n\geq n_0: f(n) < c \ g(n)$$

Can also be expressed as a limit (i guess this assumes the limit exists): $$f(n)\in o(g(n)) \iff \lim_{n\to\infty}\frac{f(n)}{g(n)}=0$$

This can be verified introducing the definition for $\lim_{n\to\infty}$ on $N$, and then both definitions are identical.

Now, the "standard" definition for big-O would be something like (near exactly to Cormen's, except the codomain here is $R^{\geq0}$): $$f(n)\in O(g(n)) \iff \exists c>0,\exists n_0>0, \forall n\geq n_0: f(n) \leq c \ g(n) \qquad (1)$$

Im trying to see if the following is true (again, this assumes the limit exists): $$f(n)\in O(g(n)) \stackrel{?}{\iff} \exists c>0: \lim_{n\to\infty}\frac{f(n)}{g(n)}=c$$

Im not sure both directions of the equivalence are true. More specifically, i am having trouble with the $\Rightarrow$. According to this general answer, both directions should be true for $\Theta(g(n))$, wich is stronger than $O(\_)$. On the contrary, this answer (for roughly the same question, but in math SE) says big-$O$ cant be defined in that way (it was downvoted).

So, the questions are:

1. How exactly def (1) implies the $\lim$ definition?:

$$\forall \epsilon>0,\exists n_0>0, \forall n\geq n_0: \left| \frac{f(n)}{g(n)}-c\right| < \epsilon$$

1. Is the above still true considering generic functions $f, \ g : X \rightarrow R^{\geq0}$, where $X$ is some reasonable domain, maybe $Z$, $N^k$ or even $R^k$ (although reals are not turing-computable, im thinking in algorithms in the more general sense possible).
• Second, in the the proposed equivalence, you are missing that $c = 0$ implies $f \in o(g) \subsetneq O(g)$. – Raphael Sep 23 '17 at 23:49
• In summary, read the definitions more carefully, and you're good. – Raphael Sep 23 '17 at 23:50
• @Raphael For your first comment, my $o$ definition is $\forall c ...$, the $O$ definition is $\exists c ...$, so i don't get what you mean with "you effectively define O". For the second, the proposed definition of $O$ with limits is with $c>0$. Could you elaborate more? – jdoes Sep 24 '17 at 0:04
• 1) Sorry, missed the different quantifier. Never mind. 2) Right, and that's why the equivalence doesn't hold. If such $c \in (0,\infty)$ exists, you have $f \in \Theta(g)$. You may want to read this. (Also, be aware that there are $f \in O(g)$ for which the limit does not exist, so the limit "definition" is not at all a definition.) – Raphael Sep 24 '17 at 1:24
• @Raphael Yes, one of the cited links in the question is to your answer, where you state that if If $c \in (0,\infty)$ exists then $f \in \Theta(g)$, but this also implies that $f \in O(g)$ and $f \in \Omega(g)$. So, let see if i finally get this, the $\Leftarrow$ direction holds, because if $f \in O(g)$ and $f \in \Theta(g)$ then is evident $f \in O(g)$, but the $\Rightarrow$ direction doesn't hold because if $f \in O(g)$, it doesn't implies also that $f \in \Theta(g)$. – jdoes Sep 24 '17 at 2:14

If $f = O(g)$ then there exists $C>0$ such that for large enough $n$, we have $f(n)/g(n) \leq C$. Hence under mild assumptions, $$f = O(g) \Longleftrightarrow \limsup_{n\to\infty} \frac{f(n)}{g(n)} < \infty.$$ As Raphael mentions in a comment to your post, your definition is symmetric in $f,g$ and so is more appropriate for $\Theta$.
• mmm.. i thought it was not an equivalence after all, also the comment on the post say the "equivalence doesn't hold" (but it does for $\Theta$), i'm missing something in your answer?. Also, what you mean with "mild assumptions"?, and why you write "... $< \infty$" instead of just "... $= C$"? they don't mean the same thing?. – jdoes Sep 24 '17 at 8:52
• The main difference between your definition and mine is that mine uses the limit superior rather than the limit. The equivalence should hold under mild assumptions such as $f,g$ being eventually positive. Finally, I write $<\infty$ since I don't care about the value of the limit superior, as long as its finite. – Yuval Filmus Sep 24 '17 at 9:12
• Ok, i see my def was to restrictive with the $c>0$ condition. So, assuming the lim exists, is your def equivalent to: $\exists c\geq0: \lim_{n\to\infty}\frac{f(n)}{g(n)}=c$ ?. By the way, sorry but i cant vote you. – jdoes Sep 24 '17 at 21:55