2
$\begingroup$

I need to prove that

$f_1 \in \Theta(g_1) \land f_2 \in \Theta(g_2) \implies f_1 + f_2 \in \Theta(\max\{g_1, g_2\})$

This question is relevant, but I have a slightly different case, so I don't know how to translate it into this one, because I need to turn the $f$'s into $g$'s.

Am I allowed to say $\max\{f_1, f_2\} \in \Theta(\max\{g_1, g_2\})$?

Or even $\Theta(\max\{f_1, f_2\}) = \Theta(\max\{g_1, g_2\})$?

$\endgroup$

1 Answer 1

3
$\begingroup$

Just notice that if $$ c_i \le \frac{f_i}{g_i} \le C_i $$ then ($n=2$ is the number of functions you are considering) $$ \frac{\max f_i}{\max g_j} \le \frac{\sum f_i}{\max g_j} = \sum_i \frac{f_i}{\max_j g_j} \le \sum \frac {f_i}{g_i}\le \sum C_i $$ and $$ \frac{\sum f_i}{\max g_j} = \sum_i \frac{f_i}{\max_j g_j} = \sum_i \min_j \frac{f_i}{g_j} \ge \sum_i \min_j \frac{f_j}{g_j} = n \min c_j $$

$\endgroup$
2
  • $\begingroup$ For the bottom part, if I try to expand the summations, should I get: $\frac{f_1 + f_2}{\max\{g_1,g_2\}} = \min\{\frac{f_1}{g_1},\frac{f_1}{g_2},\frac{f_2}{g_1},\frac{f_2}{g_2}\} \ge \min\{\frac{f_1}{g_1},\frac{f_2}{g_2}\}$? $\endgroup$ Nov 27, 2013 at 21:29
  • $\begingroup$ I have modified the bottom part, it was wrong. $\endgroup$ Nov 28, 2013 at 12:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .