2
$\begingroup$

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?

  • 1
    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".2012-10-14
  • 0
    Also, there should be a definition with $\iff$.2012-10-14

1 Answers 1