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

Question

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!

Answer 1

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.

This is why, imho, first should be taken as base definition and second considered only in appropriate situations and why I count your question important.

If such subsequence does not exist, then your proof is correct.