How do I prove/disprove $f(n) = O(g(n))$ implies $g(n) = O(f(n))$?
I got to $f(n) \le c * g(n)$ easily enough from the definition of Big O, but I'm not sure how to get to $c*f(n) \ge g(n)$.
Asked
Active
Viewed 3,983 times
3
-
Sometimes people misuse $O$ when they mean $\Theta$. That might lead to it seeming like the implication is true. – Mark S. Dec 15 '13 at 20:08
1 Answers
7
NO. $f(x)=x, g(x)=x^2$ is a counterexample.
Ma Ming
- 7,482
-
2Ah. That would explain why I was stuck. I kept trying to prove it, when I should be disproving it. – too careful May 05 '13 at 00:21