I have been asked to show that:
$$ \mathcal{O}(Max\{ f(n), g(n) \}) = \mathcal{O}(f(n) + g(n)) $$
I have seen explanations of similar problems, but this is the first time I have encountered the equals ($=$) sign being used to describe a relationship between two complexity classes (e.g.—$ \mathcal{O}(f) = \mathcal{O}(g) $).
Here is my attempt at the problem:
If $f(n) > 0$ and $g(n) > 0$ for all $n \geq n_{0}$, then
$f(n) < f(n) + g(n)$, and
$g(n) < f(n) + g(n)$.
Therefore, by definition, $f(n) \in \mathcal{O}(f(n) + g(n))$ and $g(n) \in \mathcal{O}(f(n) + g(n))$. Given that $Max\{f(n), g(n)\}$ must be either $f(n)$ or $g(n)$, it follows then that:
$$Max\{f(n), g(n)\} \in \mathcal{O}(f(n) + g(n)).$$
However, I am not sure whether showing this is the same as showing: $$ \mathcal{O}(Max\{ f(n), g(n) \}) = \mathcal{O}(f(n) + g(n)). $$
For example, if I know that $n^2+1 \in \mathcal{O}(n^2)$, may I then write that $\mathcal{O}(n^2+1)$ equals $\mathcal{O}(n^2)$? I understand that such a relationship is not necessarily symmetric (as might be suggested by the '$=$' symbol); would this statement simply imply that $\mathcal{O}(n^2+1) \subseteq \mathcal{O}(n^2)$?
I'd greatly appreciate any clarification and feedback on my approach. I may have completely missed the mark here.
To show that $f(n) + g(n) \in \mathcal{O}(\text{Max}\{f(n),g(n)\})$, note that $f(n) \le \text{Max}\{f(n),g(n)\}$ and $g(n) \le \text{Max}\{f(n),g(n)\}$. So, what do you know about $f(n)+g(n)$?
After you've shown $\text{Max}\{f(n),g(n)\} \in \mathcal{O}(f(n)+g(n))$ and $f(n)+g(n) \in \mathcal{O}(\text{Max}\{f(n),g(n)\})$, then you know that $\mathcal{O}(\text{Max}\{f(n),g(n)\}) = \mathcal{O}(f(n)+g(n))$.