$f(n)=\Theta(g(n))\iff f(n)\sim g(n)$?

Question

In this table the two expressions $f(n)=\Theta(g(n))$ ("$f$ is bounded both above and below by g asymptotically") and $f(n)\sim g(n)$ ("$f$ is equal to $g$ asymptotically") are written in two separate lines. But am I write that they mean the same thing?

Answer 1

No. Constants matter.

For instance, $f(x) = x$ and $g(x)=2x$ satisfy $f(n) =\Theta(g(n))$ (for $n\to\infty$), but we do not have $$ f(n) \operatorname*{\sim}_{n\to\infty} g(n)\,, $$ which would mean $\lim_{n\to\infty} \frac{f(n)}{g(n)}=1$. We do have $$ f(n) \operatorname*{\sim}_{n\to\infty} \frac{1}{2}g(n)\,. $$

In short: $\sim$ is more refined, a strictly stronger statement. You have one implication of what you wrote, but not the equivalence.

Answer 2

Perhaps $f(n)=\Theta(g(n))$ means $$ 0 < \liminf \frac{f(n)}{g(n)} \le \limsup \frac{f(n)}{g(n)} < +\infty $$ while $f(n)\sim g(n)$ means $$ \lim\frac{f(n)}{g(n)} = 1 $$

Answer 3

The main difference I think, is you wouldn't say $$f(n)=n^3\sim g(n)=4n^3.$$ But $f(n)\in\Theta(g(n))$ in the case. In other words, "$\sim$" requires two functions behave almost the SAME, besides being bounded above and below.