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

Question

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)$?

Answer 1

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))$.

Answer 2

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