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}\]


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