1

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

I saw a proof of this from the site from way back. I am not convinced this is true with the statement THEN between. This is Transpose symmetry I think and the statement in between Prove should be Prove that if $f(n)\in O(g(n))$ IF AND ONLY IF $g(n)\in\Omega(f(n))$. Can anyone elaborate

mrtaurho
  • 16,103
david
  • 9
  • Look at the definition of the two statements. Type them out. It should be nearly obvious that they are equivalent. – Arthur Feb 27 '21 at 12:04
  • It is to me but I saw the transpose symmetry and it had IF and Only if which is stronger than then – david Feb 27 '21 at 12:07

1 Answers1

2

The if and only if is true.
If $f(n) \in O(g(n))$ then there is some $N$ and $k>0$ such that for $n \geq N$, $$f(n) \leq k g(n).$$ This means that for $n \geq N$, $g(n) \geq \frac{1}{k} f(n)$,i.e. , $g(n) \in \Omega(f(n))$.
The other way around is very similar.

Babado
  • 1,306