Exercise 3.1.5

Prove Theorem 3.1

The theorem states:

For any two functions $f(n)$ and $g(n)$, we have $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$.

From $f(n) = \Theta(g(n))$, we have that:

$$ 0 \leq c_1g(n) \leq f(n) \leq c_2g(n) \quad \text{for } n > n_0$$

We can pick the constants from here and use them in the definitions of $O$ and $\Omega$ to show that both hold.

From $f(n) = \Omega(g(n))$ and $f(n) = O(g(n))$:

$$ 0 \leq c_3g(n) \leq f(n) \quad \text{for all } n \geq n_1 \\ 0 \leq f(n) \leq c_4g(n) \quad \text{for all } n \geq n_2 $$

If we let $n_3 = \max(n_1, n_2)$ and merge the inequalities, we get:

$$ 0 \leq c_3g(n) \leq f(n) \leq c_4g(n) \quad \text{for all } n > n_3 $$

Which is the definiition of $\Theta$.