3
$\begingroup$

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.

  • 0
    Note that $f = O(G)$ and $O(f) + O(g)$ and similar expressions are abuse of notation that often leads to misconceptions. $O(.)$ denotes a *class* of functions, so a function can not be equal to it, nor can you calculate with them as if they were numbers.2011-03-06

1 Answers 1

2

$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)| \}).$