I am having a hard time proving that $\Theta(\max(f,g)) = \Theta(f+g) $
where
$(f+g)(n) = f(n) + g(n) $
and
$(\max{f,g})(n) = \max(f(n), g(n))$
I know that $\Theta$ is the combination of the upper and lower bounds, but I can't seem to prove this. It's hard for me to see how $\Theta$ of the max of two functions can be equivalent to $\Theta$ of the two functions added together. Any guidance would be appreciated. Let me know if I can provide more info.
Best Answer
Certainly, $\max(f,g) \leq f+g$ so $\max(f,g) = O(f+g)$, and it only remains to establish the lower bound.
If $f = \Theta(g)$, the statement is trivial, so assume $f = O(g)$ and then $2 \max(f,g) = 2g \geq f+g$, which implies $\max(f,g) = \Omega(f+g)$, as desired.