Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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. – Jebruho Dec 17 '12 at 0:07
If $f$ is $O(g)$, then $g$ is $\Omega(f)$. – Brian M. Scott Dec 17 '12 at 0:07
@Jebruho: The wording is a little sloppy in places, but the question is perfectly understandable. – Brian M. Scott Dec 17 '12 at 0:08
@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. – Bailor Tow Dec 17 '12 at 0:09
up vote 1 down vote accepted

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

share|cite|improve this answer
So what's the difference between $\Theta$ and $O$ if they both bound the function above? – Bailor Tow Dec 17 '12 at 0:14
@BailorTow: $f$ is $\Theta(g)$ if and only if $f$ is both $O(g)$ and $\Omega(g)$. – Brian M. Scott Dec 17 '12 at 0:21
Oh, OK. So then $g$ is also $O(f)$? – Bailor Tow Dec 17 '12 at 0:23
@BailorTow: Yes: loosely speaking the two functions have the same order of magnitude. – Brian M. Scott Dec 17 '12 at 0:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.