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