7.2.3 Theta

The function $\Theta(f)$ denotes the set of functions that grow at the same rate as $f$. It is the intersection of the sets $O(f)$ and $\Omega(f)$. Hence, a function $g$ is in $\Theta(f)$ if and only if $g$ is in $O(f)$ and $g$ is in $\Omega(f)$. In Figur 7.2, $\Theta(f)$ is the ring between the outer and inner circles.

An alternate definition combines the inequalities for $O$ and $\Omega$:

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

$$ c_1 f(n) \ge g(n) \ge c_2 f(n). $$

If $g(n)$ is in $\Theta(f(n))$, then the sets $\Theta(f(n))$ and $\Theta(g(n))$ are identical. If $g(n) \in \Theta(f(n))$ then $g$ and $f$ grow at the same rate,

Example 7.3: $\Theta$ Examples

Determining membership in $\Theta(f)$ is simple once we know membership in $O(f)$ and $\Omega(f)$. $n-7$ is in $\Theta(n+12)$
Since $n-7$ is in $O(n+12)$ and $n-7$ is in $\Omega(n+12)$ we know $n-7$ is in $\Theta(n+12)$. Intuitively, $n-7$ increases at the same rate as $n+12$, since adding one to $n$ adds one to both function outputs. We can also show this using the definition of $\Theta(f)$: choose $c_1 = 1$, $c_2 = \frac{1}{2}$, and $n_0 = 38$. \cut{ We choose the value of $c_1$ as the value of $c$ in the $O(f)$ proof, $c_2$ as the value of $c$ in the $\Omega(f)$ proof, and $n_0$ as the maximum value of the $n_0$ values from the $O(f)$ and $\Omega(f)$ proofs.}

$2n$ is in $\Theta(3n)$
$2n$ is in $O(3n)$ and in $\Omega(3n)$. Choose $c_1 = 1$, $c_2 = \frac{1}{3}$, and $n_0 = 1$.

$n$ is not in $\Theta(n^2)$
$n$ is not in $\Omega(n^2)$. Intuitively, $n$ grows slower than $n^2$ since increasing $n$ by one always increases the value of the first function, $n$, by one, but increases the value of $n^2$ by $2n + 1$, a value that increases as $n$ increases.

$n^2$ is not in $\Theta(n)$
$n^2$ is not in $O(n)$.

$n-2$ is not in $\Theta(\mathrm{Fibonacci}(n+1))$
$n-2$ is not in $\Omega(n)$.

$\mathrm{Fibonacci}(n)$ is not in $\Theta(n)$
$\mathrm{Fibonacci}(n+1)$ is not in $O(n-2)$.

Properties of $O$, $\Omega$, and $\Theta$. Because $O$, $\Omega$, and $\Theta$ are concerned with the asymptotic properties of functions, that is, how they grow as inputs approach infinity, many functions that are different when the actual output values matter generate identical sets with the $O$, $\Omega$, and $\Theta$ functions. For example, we saw $n-7$ is in $\Theta(n+12)$ and $n+12$ is in $\Theta(n-7)$. In fact, every function that is in $\Theta(n-7)$ is also in $\Theta(n+12)$.

More generally, if we could prove $g$ is in $\Theta(an+k)$ where $a$ is a positive constant and $k$ is any constant, then $g$ is also in $\Theta(n)$. Thus, the set $\Theta(an+k)$ is equivalent to the set $\Theta(n)$.

We prove $\Theta(an+k) \equiv \Theta(n)$ using the definition of $\Theta$. To prove the sets are equivalent, we need to show inclusion in both directions.

$\Theta(n) \subseteq \Theta(an+k)$
For any function $g$, if $g$ is in $\Theta(n)$ then $g$ is in $\Theta(an+k)$. Since $g$ is in $\Theta(n)$ there exist positive constants $c_1$, $c_2$, and $n_0$ such that $c_1 n \ge g(n) \ge c_2 n$. To show $g$ is also in $\Theta(an+k)$ we find $d_1$, $d_2$, and $m_0$ such that $d_1 (an + k) \ge g(n) \ge d_2 (an+k)$ for all $n \ge m_0$. Simplifying the inequalities, we need $(ad_1)n + kd_1 \ge g(n) \ge (ad_2)n + kd_2$. Ignoring the constants for now, we can pick $d_1 = \frac{c_1}{a}$ and $d_2 = \frac{c_2}{a}$. Since $g$ is in $\Theta(n)$, we know

$$ (a\frac{c_1}{a})n \ge g(n) \ge (a\frac{c_2}{a})n $$

is satisfied. As for the constants, as $n$ increases they become insignificant. Adding one to $d_1$ and $d_2$ adds $an$ to the first term and $k$ to the second term. Hence, as $n$ grows, $an$ becomes greater than $k$.

$\Theta(an + k) \subseteq \Theta(k)$
For any function $g$, if $g$ is in $\Theta(an+k)$ then $g$ is in $\Theta(n)$. Since $g$ is in $\Theta(an+k)$ there exist positive constants $c_1$, $c_2$, and $n_0$ such that $c_1 (an+k) \ge g(n) \ge c_2 (an+k)$. Simplifying the inequalities, we have $(ac_1)n + kc_1 \ge g(n) \ge (ac_2)n + kc_2$ or, for some different positive constants $b_1 = ac_1$ and $b_2 = ac_2$ and constants $k_1 = kc_1$ and $k_2=kc_2$, $b_1n + k_1 \ge g(n) \ge b_2 n + k_2$. To show $g$ is also in $\Theta(n)$, we find $d_1$, $d_2$, and $m_0$ such that $d_1 n \ge g(n) \ge d_2 n$ for all $n \ge m_0$. If it were not for the constants, we already have this with $d_1 = b_1$ and $d_2 = b_2$. As before, the constants become inconsequential as $n$ increases.

This property also holds for the $O$ and $\Omega$ operators since our proof for $\Theta$ also proved the property for the $O$ and $\Omega$ inequalities.

This result can be generalized to any polynomial. The set $\Theta(a_0 + a_1 n + a_2 n^2 + ... + a_kn^k)$ is equivalent to $\Theta(n^k)$. Because we are concerned with the asymptotic growth, only the highest power term of the polynomial matters once $n$ gets big enough.

Exercise 7.6. Repeat Exercise 7.2 using $\Theta$ instead of $O$.
Exercise 7.7. Show that $\Theta(n^2-n)$ is equivalent to $\Theta(n^2)$.
Exercise 7.8. $\left[\star \right]$ Is $\Theta(n^2)$ equivalent to $\Theta(n^{2.1})$? Either prove they are identical, or prove they are different.
Exercise 7.9. $\left[\star \right]$ Is $\Theta(2^n)$ equivalent to $\Theta(3^n)$? Either prove they are identical, or prove they are different.