# Equivalene of big O definitions (Limit Definition $\Longleftrightarrow$ Quantifier Definition)

I need to proof, that both definitions of the Big 0 notation are equiavlent, but I am not sure if my proof works both ways of the equivalence.

Definitions:
Let f,g be functions.

1. $$f(n)\in \mathcal{O}(g)\Longleftrightarrow \exists c>0\exists n_0 \forall n\geq n_0 :f(n)\leq cg(n)$$
2. $$f(n)\in \mathcal{O}(g)\Longleftrightarrow \limsup\limits_{n\to\infty}\frac{f(n)}{g(n)}<\infty$$

My proof:
$$f(n)\in \mathcal{O}(g)\Longleftrightarrow \limsup\limits_{n\to\infty}\frac{f(n)}{g(n)}<\infty$$
$$\Longleftrightarrow \exists c>0 : \limsup\limits_{n\to\infty}\frac{f(n)}{g(n)}\leq c$$
$$\Longleftrightarrow \exists c>0\exists n_0 \forall n\geq n_0 : \frac{f(n)}{g(n)}\leq c$$
$$\Longleftrightarrow \exists c>0 \exists n_0 \forall n\geq n_0 : \frac{f(n)}{cg(n)}\leq 1$$
$$\Longleftrightarrow \exists c>0 \exists n_0 \forall n\geq n_0 :f(n)\leq cg(n)$$
$$\Longleftrightarrow f(n)\in \mathcal{O}(g)$$

I would like to know, if the conversion is correct or if I made any mistakes. Thanks in advance!

• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. – D.W. Nov 9 '20 at 22:22

This 2 definitions, of course, are not equivalent, when $$g$$ have $$0$$ subseuquence i.e. when $$\exists n_k \in \mathbb{N}, n_{k+1}>n_k , k\in \mathbb{N}$$ such that $$g(n_k)=0$$. In this case, assuming, that $$\frac{0}{0}$$ have no sense as well as $$\frac{a}{0}, a \ne 0$$, then $$\frac{f(n_k)}{g(n_k)}$$ is not defined, while definition with quantifiers have no problem.
• Yes you are correct. I forgot to mention that I assume that I pressuposed $g(n)>0$. Thanks a lot! – Florian Bauer Nov 10 '20 at 9:06