0
$\begingroup$

I'm asked to show if the following is true or false:

f $\in$ $o(g)$ implies f $\notin$ $\Omega(g)$.

I suppose it should be false, then if a function f grows much slower than g, it can't at the same time grow at least as fast as g. Is this correct?

2 Answers 2

1

Going with the definitions from here: http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations

If we have $f(n) \in \Omega(g(n))$ this means that $f(n) \geq g(n)\cdot k$ for sufficiently large $n$, for some positive $k$.

If $f(n) \in o(g(n))$, this means that for sufficiently large $n$, $|f(n))| \leq |g(n)|\cdot \alpha$ for all $\alpha$.

These conditions are not mutually exclusive. An easy counterexample to such a claim is the configuration $f(x) = g(x) = c$, where $c$ is a constant. This satisfies both conditions at the same time; we just take $k = \alpha = 1$.

Thus, briefly, $\in o$ does not imply $\notin \Omega$.

1

HINT: Try to prove the contrapositive i.e., $f \in \Omega(g)$, then $f \notin o(g)$.

If $f \in \Omega(g)$, then we have that $\exists C,x_0$ such that for all $x > x_0$, we have that $f(x) \geq C g(x)$.

If $f \in o(g)$, then given any $\epsilon > 0$, $\exists x_1$ such that for all $x > x_1$, we have $\displaystyle \frac{f(x)}{g(x)} \leq \epsilon$.

Choose $\displaystyle \epsilon = \frac{C}{2}$ and see if there exists a $x_1$.

  • 0
    @Marvis: Thanks a lot!2012-04-25