0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ you forget the absolute values in the definitions. The big O represent a bound (upper bound and lower bound) to some function. $\endgroup$ – Masacroso Jul 18 '17 at 19:50
  • 4
    $\begingroup$ You can't use limits, since the limit needn't exist. For example, $\sin(n) \in O(1)$ when $n \to \infty$. $\endgroup$ – MathematicsStudent1122 Jul 18 '17 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.