0
$\begingroup$

Why is this the case? I understand that if $f(n) = \Theta (g(n))$ then $c_1g(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))$.

  • 0
    @Jebruho The exact question is: True or false: $[f(n) = \Theta (g(n))] \rightarrow [g(n) = \Omega (f(n))]$. The answer is apparently true, but I don't understand why.2012-12-17

1 Answers 1

1

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

  • 0
    @BailorTow: Yes: loosely speaking the two functions have the same order of magnitude.2012-12-17