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


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

| cite | improve this answer | |
  • $\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$ – Sammi De Guzman Nov 27 '13 at 21:29
  • $\begingroup$ I have modified the bottom part, it was wrong. $\endgroup$ – Emanuele Paolini Nov 28 '13 at 12:14

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.