Q:

The big O notation

Hey guys,
I have this ex in Data structure course.
This ex is about big o notation, and as far I remember It means that $f_1$ and $f_2$ bound asymptotically $g_1, g_2,$ but i'm not quite sure.
The question:
$f_1(n)=O(g_1(n)),  f_2(n)=O(g_2(n))$
Two functions are from and to the natural numbers.
I need to prove:
$f_1(n)+f_2(n) = O(\max\{g_1(n),g_2(n)\})$
Thank you for the help.

A:

$f_1(n)=O(g_1(n))$ (for $n\to\infty$) means that $|f_1(n)| \leq C_1 |g_1(n)|$ $\forall n> n_1$ with $C_1$ and $n_1$ finite positive numbers. Similarly for $f_2(n)=O(g_2(n))$ yields $|f_2(n)| \leq C_2 |g_2(n)|$ $\forall n> n_2$. (see http://en.wikipedia.org/wiki/Big_O_notation)
Using the triangle inequality, we get $$|f_1(n) + f_2(n)| \leq |f_1(n)| + |f_2(n)| \leq C_1 |g_1(n)| + C_2 |g_2(n)| \qquad \forall n> \max\{n_1,n_2\}.$$ 
Using that both $|g_1|$ and $|g_2|$ are bounded from above by $\max\{|g_1|, |g_2|\}$, we obtain
$$|f_1(n) + f_2(n)| \leq (C_1 + C_2) \max \{ |g_1(n)| , |g_2(n)| \} \qquad n>\max\{n_1,n_2\},$$
or in terms of big-O notation
$$f_1(n) + f_2(n)  = O (\max \{ |g_1(n)| , |g_2(n)| \}).$$

