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

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

score 4 · Answer 1 · answered Mar 23 '15 at 01:54

4

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

answered Mar 23 '15 at 01:54

MathMajor

6,478

3

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 02:43
Yes, it was just one counter example :) – MathMajor Mar 24 '15 at 04:26

score 2 · Accepted Answer · answered Mar 23 '15 at 03:35

2

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

answered Mar 23 '15 at 03:35

marty cohen

107,799

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

2 Answers2