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.

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!

  • $\begingroup$ 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. $\endgroup$ – 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.

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.

  • $\begingroup$ Yes you are correct. I forgot to mention that I assume that I pressuposed $g(n)>0$. Thanks a lot! $\endgroup$ – Florian Bauer Nov 10 '20 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.