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