Prove that $\mathcal{O}(f_{1}(x)+ \dots +f_{n}(x))= \mathcal{O}(\max(f_{1}(x), \dots ,f_{n}(x)))$

Question

I want to prove the following that based on maximum rule of functions: $$\mathcal{O}(f_{1}(x)+ \dots +f_{n}(x))= \mathcal{O}(\max(f_{1}(x), \dots ,f_{n}(x)))$$ the base prove is for each 2 functions : $$\mathcal{O}(f(n)+g(n))= \mathcal{O}(\max(f(n),g(n)))$$
Note that the functions are not negative.
I would like to get some advice how to prove for a set of functions with induction.
what I tried to do is to take each 2 functions, get the max between them and check the result with the next function, there is another way to think about that?
thanks!

Answer 1

Another way would be to go back to the definition to prove $g \in \mathcal{O}(f_{1}(x)+ \dots +f_{n}(x)) \leftrightarrow g \in \mathcal{O}(\max(f_{1}(x), \dots ,f_{n}(x))$:

$g \in \mathcal{O}(f_{1}(x)+ \dots +f_{n}(x))$ implies:

$\exists k>0 \; \exists n_0 \; \forall n>n_0 \; g(n) \leq (f_{1}(x)+ \dots +f_{n}(x))\cdot k$ implies:

$\exists k>0 \; \exists n_0 \; \forall n>n_0 \; g(n) \leq (\max(f_{1}(x), \dots ,f_{n}(x))\cdot kn$ implies:

$\exists K>0 \; \exists n_0 \; \forall n>n_0 \; g(n) \leq (\max(f_{1}(x), \dots ,f_{n}(x))\cdot K$ implies:

$g \in \mathcal{O}(\max(f_{1}(x), \dots ,f_{n}(x))$

Since $\max(f_{1}(x), \dots ,f_{n}(x)) \leq f_{1}(x)+ \dots +f_{n}(x)$, the reciprocal is straightforward.

Answer 2

Hint:

• The number $n$ is a constant with regard to a single formula.
• You need to assume that $f_i(x) \geq 0$ for all $i$, otherwise weird things might happen.
• $(\Rightarrow)$ For all $x$ we have $$\sum_{i=1}^{n} f_i(x) \leq n \cdot \max_{i=1}^{n} f_i(x).$$
• $(\Leftarrow)$ We have, for all $x$, $$\max_{i=1}^{n} f_i(x) \leq \sum_{i=1}^{n} f_i(x).$$
• I'm only guessing you want to prove it both ways. Be aware that notation $g(x) = \mathcal{O}(f(x))$ is unfortunate, esp. the equality sign "$=$" suggests some kind of a symmetry which is not there. Some prefer to use $g(x) \in \mathcal{O}(f(x))$ – it's not perfect, but still much better.

I hope this helps $\ddot\smile$