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.

Prove that if $f(n) \in O(g(n))$ then $g(n) \in \Omega(f(n))$.

So I know that

$$O(g(n)) \Rightarrow f(n) \leq c\cdot g(n)$$

and that

$$\Omega(g(n)) \Rightarrow f(n) \geq c\cdot g(n)$$

but how do you use these to do the above proof?

share|improve this question
    
Your problem is with mathematical rigour. The definition of big oh you state is not complete. It is that "there exists" a positive constant" $c$ with that property "for sufficiently large n". –  fretty Oct 14 '12 at 12:32
    
Also, there should be a definition with $\iff$. –  Raphael Oct 14 '12 at 16:38
add comment

1 Answer

I'm not quite sure what definitions you are working with, but for $f, g : \mathbb{N} \to \mathbb{N}$ I'd say $f(n)$ is (or $\in$) $O(g(n))$ if there is a constant $c > 0$ and $N \in \mathbb{N}$ such that $f(n) \leq c\cdot g(n)$ for all $n \geq N$; and similarly for $f(n)$ is $\Omega(g(n))$.

As $f(n)$ is $O(g(n))$ there is a constant $c > 0$ and $N \in \mathbb{N}$ such that

$$f(n) \leq c\cdot g(n)$$

for all $n \geq N$. Rearranging this inequality, we have

$$\frac{1}{c}\cdot f(n) \leq g(n)$$

for all $n \geq N$. Letting $K = \frac{1}{c}$ we can rewrite this inequality as

$$g(n) \geq K\cdot f(n)$$

for all $n \geq N$. As $c > 0$, $K > 0$, so this inequality shows that $g(n)$ is $\Omega(f(n))$.

share|improve this answer
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.