4
$\begingroup$

This may be a dumb question, but if $f(n)\in O(g(n))$ can $g(n)\in O(f(n))$? I can think of a few counter examples, like $n\in O(n^2)$ and obviously $n^2\notin O(n)$, but one counter example doesn't deny the existence of one case where it is true. Is this true or false? And how can I prove it either way?

Thanks!!

  • 7
    What if $f(x)=g(x)$? ;)2012-09-07
  • 1
    It's hard for me to understand what *exactly* you want: you already provided a counterexample, thus the question to your post's heading is: NO. Now, there are some cases when it can happen, for example if both functions are constants...2012-09-07
  • 0
    @N.S. How did I not think of that?? Thanks!2012-09-07
  • 0
    @DonAntonio His example shows that the question he asks is sometimes NOT true, his "counter-example" is not a counterexample. It just shows that the implication is not always true, but the question is if it CAN be true?2012-09-07
  • 4
    There is in fact a term for such a scenario as $f\in O(g)\wedge g\in O(f)$. We say that $f=\Theta(g)$ (which is an equivalence relation, i.e. it's equivalent to $g=\Theta(f)$). See [Wikipedia's table](http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations).2012-09-07

1 Answers 1

3

Yes, it's certainly true. We say that $f(n)\in O(g(n))$ if there exists a constant $C_1$ such that $\lvert{f(n)}\rvert < C_1\lvert g(n) \rvert$ for sufficiently large $n$, and similarly $g(n)\in O(f(n))$ if there exists $C_2$ such that $\lvert{g(n)}\rvert < C_2\lvert f(n)\rvert$ for sufficiently large $n$. These both hold if there are constants $A$ and $B$ such that $A\lvert g(n) \rvert < \lvert{f(n)}\rvert < B\lvert g(n) \rvert$ for sufficiently large $n$, or equivalently such that $$ A < \left\lvert{\frac{f(n)}{g(n)}}\right\rvert < B. $$ In this case we say that $f(n)\in\Theta(g(n))$. The relation is symmetric and transitive, and obviously reflexive, so it defines an equivalence relation on the set of functions.