# Suppose $f_1 \in \Theta(g_1) \land f_2 \in \Theta(g_2)$. Prove $f_1 + f_2 \in \Theta(\max\{g_1, g_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\})$?

## 1 Answer

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

• 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}\}$? Nov 27, 2013 at 21:29
• I have modified the bottom part, it was wrong. Nov 28, 2013 at 12:14