Suppose that $f(x)\sim g(x)$, then does $f(x)=O(g(x))$? Conversely, suppose that $f(x)=O(g(x))$, then does $f(x)\sim g(x)$?
Asked
Active
Viewed 43 times
1
-
The first statement is true, the second is not. – Ben Grossmann Dec 21 '20 at 18:43
-
Strictly speaking, by $=O$ you mean $\in O$. You may be interested to notice $f\sim g\iff f-g\in o(g)$. – J.G. Dec 21 '20 at 19:04
1 Answers
1
It is useful to recognize that
- "$f(x)=O(g(x))$" is equivalent to "there exists a constant $C$ such that $\left|\frac{f(x)}{g(x)}\right| \le C$ for sufficiently large $x$."
- $f(x) \sim g(x)$ is defined as $\frac{f(x)}{g(x)} \to 1$.
From here, we immediately see that $f(x) \sim g(x)$ implies $f(x)=O(g(x))$ (take $C=2$, for instance).
However, the converse does not hold. For example, $f(x)=2x$ and $g(x)=x$ satisfy $\frac{f(x)}{g(x)} \le 2$ but $\frac{f(x)}{g(x)} \not\to 1$.
angryavian
- 89,882