Prove Theorem 3.1 which 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))\).

Suppose \(f(n) = \Theta(g(n))\). Then, by definition there exist positive constants \(c_1\), \(c_2\), and \(n_0\) such that \(0 \leq c_1g(n) \leq f(n) \leq c_2g(n) \ \forall \ n \geq n_0\). Due to the existence of \(c_1\) and \(n_0\), it is true that \(0 \leq c_1g(n) \leq f(n) \ \forall \ n \geq n_0 \implies f(n) = \Omega(g(n))\). Likewise the existence of \(c_2\) and \(n_0\) make it true that \(0 \leq f(n) \leq c_2g(n) \ \forall \ n \geq n_0 \implies f(n) = O(g(n))\).

That being said, the “if and only if” wording means we must also prove that the inverse holds as well.

Suppose \(f(n) = O(g(n))\) and \(f(n) = \Omega(g(n))\). Then, by definition there exist positive constants \(c_a\), \(c_b\), \(n_{a}\) and \(n_{b}\) such that:

\[0 \leq c_ag(n) \leq f(n) \ \forall \ n > n_a\] \[0 \leq f(n) \leq c_bg(n) \ \forall \ n > n_b\]

By setting \(n_c = \max(n_a, n_b)\) we can combine these two inequalities:

\[0 \leq c_ag(n) \leq f(n) \leq c_bg(n) \ \forall \ n > n_c \implies f(n) = \Theta(g(n))\]