1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.