0
$\begingroup$

$f(n) = \mathcal{o}(g(n))$ if for any constant $c$, there exists some constant $n_0$ such that $0 \le f(n) \le cg(n), n \ge n_0 $

$f(n) = \pi(g(n))$ if for any constant $c$, there exists some constant $n_0$ such that $0 \le f(n) < cg(n), n \ge n_0 $

Are both the above definitions equivalent? In other words is the following true:

$$f(n) = \mathcal{o}(g(n)) \leftrightarrow f(n) = \pi(g(n))$$

$\endgroup$
2
  • 1
    $\begingroup$ Of course, $\Leftarrow$ is true as $<$ implies $\leq$. But the reverse implication does not hold in general due to possible vanishing issues. E.g. $f(n)=g(n)=0$. $\endgroup$
    – Julien
    Apr 6 '13 at 20:09
  • $\begingroup$ Also, the usual definition involves some absolute values. $\endgroup$ Apr 6 '13 at 20:11
0
$\begingroup$

Yes, they are equivalent, provided that $g$ is a positive function. It’s clear that if $f$ is $\pi(g)$, then $f$ is $o(g)$. Conversely, if for each $c>0$ you have an $n_c$ such that $0\le f(n)\le cg(n)$ for $n\ge n_c$, then you have $0\le f(n)\le\frac{c}2g(n)<cg(n)$ for all $n\ge n_{c/2}$, say.

$\endgroup$

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.