Big O notation: How can you prove this by using limits? $f \in O(g) \Leftrightarrow g \in \Omega(f)$

242 Views Asked by At

Prove that $f \in O(g) \Leftrightarrow g \in \Omega(f)$

I'm curious how that could be shown using limits or another way than the one I'm going to use?

Because I don't know another way than this (not even sure if it's alright) :

For the proof we assume that we have defined $f \in O(g) \Leftrightarrow \exists c \exists n_0 \forall n \geq n_0: f(n) \leq c \cdot g(n)$ and $f \in \Omega(g) \Leftrightarrow \exists c \exists n_0 \forall n \geq n_0: f(n) \geq c \cdot g(n)$

Now we are supposed to show that $f \in O(g) \Leftrightarrow g \in \Omega(f)$, so we have $$f \in O(g) \Leftrightarrow \exists c \exists n_0 \forall n \geq n_0: f(n) \leq c \cdot g(n) \Leftrightarrow \text{ for }c' = \frac{1}{c} \text{ and for }n_0 \text{ we have that } \forall n \geq n_0: g(n) \geq c' \cdot f(n) \Leftrightarrow g \in \Omega(f)$$


Is there a more soft proof for this? I'm thinking about using limits:

Assume we have defined

$$\lim_{n\rightarrow \infty} \frac{f(n)}{g(n)}< \infty \Rightarrow f \in O(g)$$

$$\lim_{n\rightarrow \infty} \frac{f(n)}{g(n)}>0 \Rightarrow f \in \Omega(g)$$

But then looking at the definitions, I have no idea where I should start and I wonder if it's possible at all? :o