Asymptotic relationship demonstration

Question

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?

Answer 1

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.

Answer 2

$$ 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.

Answer 3

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