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$
9
  • $\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, 2017 at 23:49
  • $\begingroup$ In summary, read the definitions more carefully, and you're good. $\endgroup$
    – Raphael
    Sep 23, 2017 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, 2017 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, 2017 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, 2017 at 2:14

1 Answer 1

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$
9
  • $\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, 2017 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$ Sep 24, 2017 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, 2017 at 21:55
  • $\begingroup$ You should be able to answer this question on your own. $\endgroup$ Sep 24, 2017 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, 2017 at 22:24

Your Answer

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

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