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
    In this question, you provide no background, and your question is unclear about how precisely you use $\Theta$ and how you use $\Omega$ and how you choose $c_{1}$ and $c_{2}$. This question, as is, is unhelpful.2012-12-17
  • 1
    If $f$ is $O(g)$, then $g$ is $\Omega(f)$.2012-12-17
  • 0
    @Jebruho: The wording is a little sloppy in places, but the question is perfectly understandable.2012-12-17
  • 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
    So what's the difference between $\Theta$ and $O$ if they both bound the function above?2012-12-17
  • 0
    @BailorTow: $f$ is $\Theta(g)$ if and only if $f$ is both $O(g)$ **and** $\Omega(g)$.2012-12-17
  • 0
    Oh, OK. So then $g$ is also $O(f)$?2012-12-17
  • 0
    @BailorTow: Yes: loosely speaking the two functions have the same order of magnitude.2012-12-17