Comparisons of functions, their big-oh and their implications

Question

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

Answer 1

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