Let \(f(n)\) and \(g(n)\) be asymptotically nonnegative functions. Using the basic definition of \(\Theta\)-notation, prove that \(\max(f(n), g(n)) = \Theta(f(n) + g(n))\).
To prove this, we have to show that there exists constants \(c_1, c_2, n_0 > 0\) such that for all \(n \ge n_0\),
\[0 \le c_1 (f(n) + g(n)) \le \max(f(n), g(n)) \le c_2 (f(n) + g(n))\]As the functions are asymptotically non-negative, we can assume that for some \(n_0 > 0\), \(f(n) \ge 0\) and \(g(n) \ge 0\). Therefore, \(n \ge n_0\),
\[f(n) + g(n) \ge \max(f(n), g(n))\]Also note that, \(f(n) \le \max(f(n), g(n))\) and \(g(n) \le \max(f(n), g(n))\)
\[\begin{aligned} f(n) + g(n) &\le 2 \max(f(n), g(n)) \\ \frac 1 2 (f(n) + g(n)) &\le \max(f(n), g(n)) \end{aligned}\]Therefore, we can combine the above two inequalities as follows:
\[0 \le \frac 1 2 (f(n) + g(n)) \le \max(f(n), g(n)) \le (f(n) + g(n)) \text { for } n \ge n_0\]So, \(\max(f(n), g(n)) = \Theta(f(n) + g(n))\) because there exists \(c_1 = 0.5\) and \(c_2 = 1\).