Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
The first step is to write a mathematical definition of the statement that $f(n)=O(g(n))$. Once you have done that, the rest is just... well, an easy exercise. –  Did Mar 6 '11 at 9:08
    
(as always) wikipedia helps en.wikipedia.org/wiki/Big_O_notation. –  Fabian Mar 6 '11 at 9:11
    
$f_1(n)+f_2(n) = O(g_1(n)) + O(g_2(n))$. What you need to show is that $O(g_1(n)) + O(g_2(n))=O(\text{max}(g_1(n),g_2(n))$. –  please delete me Mar 6 '11 at 10:32
    
why? and how can I do that? Thanks. –  user6163 Mar 6 '11 at 10:45
    
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. –  Raphael Mar 6 '11 at 15:25

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.