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