# Big-O Analysis: Max Bounded by the Sum

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.

• The use of an equals sign is generally considered an abuse of notation, it's really a one way equality. So it's better to use $\in$. – Silynn Jun 22 '14 at 21:14

## 1 Answer

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

• Thanks for the clear response! – Michael Zalla Jun 22 '14 at 21:51