Chapter 3 Exercise 3.1-1, Introduction to Algorithms, 3rd Edition Thomas H. Cormen

3.1-1 Let f(n) and g(n) be asymptotically non-negative functions. Using the basic definition of Θ-notation, prove that max(f(n),g(n))=Θ(f(n)+g(n)).

Solution:

 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 Far
$$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 f(n) + g(n) \le 2 \max(f(n), g(n)) \\ \Rightarrow \frac 1 2 (f(n) + g(n)) \le \max(f(n), g(n))$$
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 = \frac 1 2$$ and $$c_2 = 1$$