Prove Theorem 3.1.

Theorem 3.1 says:

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

To prove this theorem, we need to show the logic holds both ways, i.e.

$f(n) = \Theta(g(n)) \implies f(n) = O(g(n)) \text {and} f(n) = \Omega(g(n)) \tag{1}$

and

$f(n) = O(g(n)) \text {and} f(n) = \Omega(g(n)) \implies f(n) = \Theta(g(n)) \tag{2}$
##### Part 1

If $$f(n) = \Theta(g(n))$$, then for $$n \ge n_0$$,

$0 \le c_1 g(n) \le f(n) \le c_2 g(n)$

As $$0 \le f(n) \le c_2 g(n)$$ for $$n \ge n_0$$, $$f(n) = O(g(n))$$.

As $$0 \le c_1 g(n) \le f(n)$$ for $$n \ge n_0$$, $$f(n) = \Omega(g(n))$$.

##### Part 2

If $$f(n) = \Omega(g(n))$$, then for $$n \ge n_1$$,

$0 \le c_1 g(n) \le f(n)$

If $$f(n) = O(g(n))$$, then for $$n \ge n_2$$,

$0 \le f(n) \le c_2 g(n)$

Combining the above two inequalities, we can say for $$n \ge max(n_1, n_2)$$,

$0 \le c_1 g(n) \le f(n) \le c_2 g(n)$

In other words, $$f(n) = \Theta(g(n))$$.