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

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|cite|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

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$, this inequality shows that $g(n)$ is $\Omega(f(n))$.

share|cite|improve this answer

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.