Big O notation sum rule I understand that when adding functions, the behavior is dominated by the highest power. But what I am having trouble is understanding the proof. Could anyone help me step by step in explaining the proof behind $T_1(n) + T_2(n) = O(max (f(n), g(n)))$ ? Thank you very much.
 A: Given $T_1(n)=O(f(n))$ and $T_2(n)=O(g(n))$, we are to prove $$T_1(n)+T_2(n)=O(\max(f(n),g(n))\tag0$$ 


*

*Write down exactly what the first assumption says: there exists a constant $C_1$ and an index $N_1$ such that 
$$|T_1(n)| \le C_1f(n)\quad \text{when } n\ge N_1 \tag1$$

*Write down exactly what the second assumption says: there exists a constant $C_2$ and an index $N_2$ such that 
$$|T_2(n)| \le C_2g(n)\quad \text{when } n\ge N_2 \tag2$$

*Prepare to combine (1) and (2) by introducing $N=\max(N_1,N_2)$ and $C=\max(C_1,C_2)$.

*Add (1) and (2): 
$$
|T_1(n)|+|T_2(n)|\le  C_1f(n)+C_2g(n) \le C(f(n)+g(n))\quad \text{when } n\ge N \tag3
$$

*Check that for any two real numbers $a,b$ we have $$a+b\le 2\max(a,b)\tag4$$

*Use (4) in (3) to obtain 
$$
|T_1(n)|+|T_2(n)|\le 2C\max(f(n),g(n))\quad \text{when } n\ge N \tag5
$$

*Conclude that (0) holds.
A: Considering non-negative functions we can say more, that sets $O(f)+O(g),O(f+g),O(\max(f,g))$ are same i.e. equality we can understand as equality between sets, not only as "$\subset$", i.e. one way direction. So we have
$$O(f)+O(g)=O(f+g)=O(\max(f,g))$$
as sets.
For proof, for example, last is enough to use $f+g\leqslant 2\cdot \max(f,g)\leqslant 2\cdot (f+g)$
