6
$\begingroup$

Question: If $f(n)$ is $O(g(n))$ and $g(n)$ is $O(f(n))$, is $f(n) = g(n)$?

I'm studying for a discrete mathematics test, and I'm not sure if this is true or false. Since Big-OH ignores constant multiples, wouldn't $f(n) = c\, g(n)$?

$\endgroup$
  • 2
    $\begingroup$ Why a close vote? The author put in a bit of context and their own idea. $\endgroup$ – Alan Mar 23 '15 at 2:00
2
$\begingroup$

Consider $f(n) = an^2$ and $g(n) = bn^2$ where $a$ and $b$ are distinct positive reals.

Both $f(n) = O(g(n))$ and $g(n) = O(f(n))$ are true, but $f(n) \ne g(n)$ for $n > 0$.

This is often written as $f(n) = \Theta(g(n))$.

$\endgroup$
4
$\begingroup$

Your thoughts are correct. Consider $f(n) = n$ and $g(n) = 2f(n)$ as a counter example.

$\endgroup$
  • 3
    $\begingroup$ But to clarify, it needn't be the case that one function is a constant multiple of the other. $\endgroup$ – Eric M. Schmidt Mar 23 '15 at 2:43
  • $\begingroup$ Yes, it was just one counter example :) $\endgroup$ – MathMajor Mar 24 '15 at 4:26

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.