7.2.2 Omega

The set $\Omega(f)$ (omega) is the set of functions that grow no slower than $f$ grows. So, a function $g$ is in $\Omega(f)$ if $g$ grows as fast as $f$ or faster.
Constrast this with $O(f)$, the set of all functions that grow no faster than $f$ grows. In Figure 7.2, $\Omega(f)$ is the set of all functions outside the darker circle.

The formal definition of $\Omega(f)$ is nearly identical to the definition of $O(f)$: the only difference is the $\le$ comparison is changed to $\ge$.

Definition of $\Omega(f)$. The function $g$ is a member of the set $\Omega(f)$ if and only if there exist positive constants $c$ and $n_0$ such that, for all values $n \ge n_0$,

$$ g(n) \ge cf(n). $$
Examples 7.2: $\Omega$ Examples

We repeat selected examples from the previous section with $\Omega$ instead of $O$. The strategy is similar: we show $g$ is in $\Omega(f)$ using the definition of $\Omega(f)$ by choosing positive constants for the values of $c$ and $n_0$, and showing that the property $g(n) \ge cf(n)$ holds for all values $n \ge n_0$. To show $g$ is not in $\Omega(f)$, we need to explain how, for any choices of $c$ and $n_0$, we can find a choice for $n \ge n_0$ such that $g(n) < cf(n)$.

$n-7$ is in $\Omega(n+12)$
Choose $c = \frac{1}{2}$ and $n_0 = 26$. Then, we need to show $n-7 \ge \frac{1}{2} (n+12)$ for all values $n \ge 26$. This is true, since the inequality simplifies $\frac{n}{2} \ge 13$ which holds for all values $n \ge 26$. % fixed 2009-12-29, Kristine Dell %\item $n+12$ is in $\Omega(n-7)$: Choose $c = 1$ and $n_0 = 1$.

$2n$ is in $\Omega(3n)$
Choose $c = \frac{1}{3}$ and $n_0 = 1$. Then, $2n \ge \frac{1}{3}(3n)$ simplifies to $n \ge 0$ which holds for all values $n \ge 1$.

$n$ is not in $\Omega(n^2)$
Whatever values are chosen for $c$ and $n_0$, we can choose $n \ge n_0$ such that $n \ge cn^2$ does not hold. Choose $n > \frac{1}{c}$ (note that $c$ must be less than 1 for the inequality to hold for any positive $n$, so if $c$ is not less than 1 we can just choose $n \ge 2$). Then, the right side of the inequality $cn^2$ will be greater than $n$, and the needed inequality $n \ge cn^2$ does not hold.

$n$ is not in $\Omega(\mathrm{Fibonacci}(n))$
No matter what values are chosen for $c$ and $n_0$, we can choose $n \ge n_0$ such that $n \ge \mathrm{Fibonacci}(n)$ does not hold. The value of $\mathrm{Fibonacci}(n)$ more than doubles every time $n$ is increased by 2 (see Section 7.2.1), but the value of $c(n)$ only increases by $2c$. Hence, if we keep increasing $n$, eventually $\mathrm{Fibonacci}(n+1) > c(n-2)$ for any choice of $c$.

Exercise 7.4 Repeat Exercise 7.2 using $\Omega$ instead of $O$.

Exercise 7.5 For each part, identify a function $g$ that satisfies the property.
a. $g$ is in $O(n^2)$ but not in $\Omega(n^2)$.
b. $g$ is not in $O(n^2)$ but is in $\Omega(n^2)$.
c. $g$ is in both $O(n^2)$ and $\Omega(n^2)$.