2

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

Community
  • 1
Sammi De Guzman
  • 155

1 Answers1

3

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

Emanuele Paolini
  • 21,447
  • 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}}$? – Sammi De Guzman Nov 27 '13 at 21:29
  • I have modified the bottom part, it was wrong. – Emanuele Paolini Nov 28 '13 at 12:14