1
$\begingroup$

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).
$\endgroup$
  • $\begingroup$ Second, in the the proposed equivalence, you are missing that $c = 0$ implies $f \in o(g) \subsetneq O(g)$. $\endgroup$ – Raphael Sep 23 '17 at 23:49
  • $\begingroup$ In summary, read the definitions more carefully, and you're good. $\endgroup$ – Raphael Sep 23 '17 at 23:50
  • $\begingroup$ @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? $\endgroup$ – jdoes Sep 24 '17 at 0:04
  • $\begingroup$ 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.) $\endgroup$ – Raphael Sep 24 '17 at 1:24
  • $\begingroup$ @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)$. $\endgroup$ – jdoes Sep 24 '17 at 2:14
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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?. $\endgroup$ – jdoes Sep 24 '17 at 8:52
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 24 '17 at 9:12
  • $\begingroup$ 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. $\endgroup$ – jdoes Sep 24 '17 at 21:55
  • $\begingroup$ You should be able to answer this question on your own. $\endgroup$ – Yuval Filmus Sep 24 '17 at 22:15
  • $\begingroup$ I am not really familiarized with lim sup/inf. Most class notes doesn't mention it, or is treated like some peculiarity. $\endgroup$ – jdoes Sep 24 '17 at 22:24

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.