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

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

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

## 2 Answers

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

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

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