Prove that $\mathcal{O}(f_{1}(x)+ \dots +f_{n}(x))= \mathcal{O}(\max(f_{1}(x), \dots ,f_{n}(x)))$ 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!
 A: 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.
A: 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$
