# Comparisons of functions, their big-oh and their implications

I don't understand why the $$1^{st}$$ is false but I think I see why the $$2^{nd}$$ is true.

1. If $$f(n) = O(n^2)$$ and $$g(n) = O(n^2)$$, then $$f(n) = O(g(n))$$.

2. If $$f(n) = O(g(n))$$ and $$g(n) = O(n^2)$$, then $$f(n) = O(n^2)$$.

I understand why the second is true but not the $$1^{st}$$. For case 1, if

• $$f(n) < c_1n^2$$ for some $$n > n_1$$ and
• $$g(n) < c_2n^2$$ for some $$n > n_2$$

by using constants instead of big-O notation , can't we find $$c_3$$ such that $$f(n) < c_3g(n)$$ for some $$n > n_3$$ ?

As a counterexample you can take $$f(n)=n$$ and $$g(n)=\sqrt{n}$$. You can think that $$f(n)=O(n^2)$$ means that an upper bound for $$f(n)$$ is $$n^2$$ (of course, without considering multiplicative constant), so the fact that both $$f$$ and $$g$$ are bounded by $$n^2$$ does not implies nothing about the relative behavior of $$f$$ and $$g$$.
• Thanks. I see that with $g(n) = \frac{1}{n}$, then this doesn't $f(n) \neq O(g(n))$ – heretoinfinity Apr 17 at 18:11