Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
1  
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
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.