Let $f(n)$ and $g(n)$ be asymptotically non-negative 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 $0 \le c_1 (f(n) + g(n)) \le \max(f(n), g(n)) \le c_2 (f(n) + g(n))$ for all $n \ge n_0$.

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

So for $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))$

Therefore, we can combine the above two inequalities as follows:

So, $\max(f(n), g(n)) = \Theta(f(n) + g(n))$ because there exists $c_1 = \frac 1 2$ and $c_2 = 1$.