Why is this the case? I understand that if $f(n) = \Theta (g(n))$ then $c_1g(n)<f(n)<c_2g(n)$, but why does this show that $g(n)$ is bounded below by $f(n)$? I would think that it would be more accurate to say that $f(n) = O(g(n))$ and $f(n) = \Omega (g(n))$.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
If $f(n)$ is $\Theta\big(g(n)\big)$, then $f(n)$ is $O\big(g(n)\big)$, and there are a positive constant $c$ and an $n_0\in\Bbb N$ such that $|f(n)|\le c|g(n)|$ for all $n\ge n_0$. But then $|g(n)|\ge\frac1c|f(n)|$ for all $n\ge n_0$, and $\frac1c>0$, so $g(n)$ is $\Omega\big(f(n)\big)$.