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?
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?
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$.
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$.