1
$\begingroup$

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!

$\endgroup$
1
  • $\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.
    Commented Nov 9, 2020 at 22:22

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes you are correct. I forgot to mention that I assume that I pressuposed $g(n)>0$. Thanks a lot! $\endgroup$ Commented Nov 10, 2020 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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