# Asymptotic relationship demonstration

I have to demonstrate that if $$\begin{split} f_1(n) &= \Theta(g_1(n)) \\ f_2(n) &= \Theta(g_2(n)) \\ \end{split}$$ then $$f_1(n) + f_2(n) = \Theta(\max\{g_1(n),g_2(n)\})$$

Actually I have already proved that $$f_1(n)+f_2(n) = O(\max\{g_1(n),g_2(n)\}).$$ My problem is $$f_1(n)+f_2(n) = \Omega(\max\{g_1(n),g_2(n)\}),$$ could you help me?

$$f_1(n) \geq c_1 g_1(n)\\ f_2 (n) \geq c_2 g_2(n)$$ wlog assume $g_1 >g_2$. Hence $$f_1 +f_2 \geq c_1g_1 +c_2g_2 \geq c_1g_1 = \Omega(g_1(n))$$ The same is true if $g_2 >g_1$. The lower bound follows.

Note that if $f = \Theta(g)$ then $g = \Theta(f)$ and since you already proved the $O()$ bound, you can conclude that $f_1 + f_2 = O(g_1 + g_2)$ and by a symmetric argument that $g_1 + g_2 = O(f_1 + f_2)$ which is equivalent to the $\Omega()$ bound you seek.

• I'm sorry but how g1+g2 is related with max{g1,g2}? – user1868607 Nov 4 '13 at 16:40
• $\max\{f,g\} = \Theta(f+g)$ – gt6989b Nov 4 '13 at 16:42

$f_1(n)=\mathbf{\theta}(g_1(n)) \Rightarrow \forall n>N_1;c_1f_1(n)\geq g_1(n)$

$f_2(n)=\mathbf{\theta}(g_2(n)) \Rightarrow \forall n>N_2;c_2f_2(n)\geq g_2(n)$

so

$\forall n>max\{N_1,N_2\};max\{c_1,c_2\}(f_1(n)+f_2(n))\geq 2 max\{g_1(n),g_2(n)\}$