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$
1
  • 2
    $\begingroup$ Why a close vote? The author put in a bit of context and their own idea. $\endgroup$
    – Alan
    Mar 23, 2015 at 2:00

2 Answers 2

4
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ But to clarify, it needn't be the case that one function is a constant multiple of the other. $\endgroup$ Mar 23, 2015 at 2:43
  • $\begingroup$ Yes, it was just one counter example :) $\endgroup$
    – MathMajor
    Mar 24, 2015 at 4:26
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .