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?

score 1 · Answer 1 · answered Nov 04 '13 at 16:39

1

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

answered Nov 04 '13 at 16:39

Alex

19,262

score 0 · Answer 2 · answered Nov 04 '13 at 16:34

0

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.

answered Nov 04 '13 at 16:34

gt6989b

54,422

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

hhsaffar · Answer 3 · 2013-11-04T16:52:27.557

0

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

edited Nov 04 '13 at 16:52

answered Nov 04 '13 at 16:46

hhsaffar

2,937

Asymptotic relationship demonstration

3 Answers3