# Prove Linearity in Asymptotic Notation

The question: Prove O($\sum\limits_{k=1}^m(f_k(n))$) = $\sum\limits_{k=1}^m(O(f_k(n)))$

What I have done so far:

Left side: Let g(n) = O($\sum\limits_{k=1}^m(f_k(n))$)
For n > c, we have g(n) $\le$ C * ($f_1$(n) + $f_2$(n) + ... + $f_m$(n))

Right side: Let h(n) = $\sum\limits_{k=1}^m(O(f_k(n)))$

h(n) $\le$ O($f_1$(n)) + O($f_2$(n)) + ... + O($f_m$(n))
h(n) $\le$ $C_1$*$f_1$(n) + $C_2$*$f_2$(n) + ... + $C_m$*$f_m$(n)

From here I'm not sure what to do. I know I can't factor out the C's because they could be different.

I was thinking if I could prove O(f(n)) + O(g(n)) = O(f(n) + g(n)) I could related it to the above since it would kind of be like putting them all together but I don't even know how to do that

• If you can prove for $m=2$, you can clearly go into recursion & be done after $m-1$ steps. But: what do you know about $\{f_n\}$? The way this stands, it can't be true - trivial example: $f_1(n)=1/n$, $f_2(n)=-f_1(n)$, $f_k(n)=1/n^k$. – automaton 3 Sep 28 '13 at 8:06

Let the sequences $\left(f_{n}\right)$ and $\left(g_{n}\right)$ satisfy $f_{n}>0$ and $g_{n}>0$ for all $n\in\mathbb{N}$. Then $\mathcal{O}\left(f_{n}\right)+\mathcal{O}\left(g_{n}\right)=\mathcal{O}\left(f_{n}+g_{n}\right)$.
Proof.Suppose $$\varphi_{n}=\mathcal{O}\left(f_{n}\right)\quad\text{and}\quad\psi_{n}=\mathcal{O}\left(g_{n}\right).$$ Then, by definition, there exist indices of these sequences $n^{\prime}\in\mathcal{\mathbb{N}}$ and $n^{\prime\prime}\in\mathbb{N}$ as well as constants $M_{1}>0$ and $M_{2}>0$ such that $\left|\varphi_{n}\right|\leq M_{1}f_{n}$ whenever $n>n^{\prime}$and $\left|\psi_{n}\right|\leq M_{2}g_{n}$whenever $n>n^{\prime\prime}$. Thus, taking $n_{0}:=\max\left\{ n^{\prime},n^{\prime\prime}\right\}$, it follows that $$\left|\varphi_{n}+\psi_{n}\right|\leq\left|\varphi_{n}\right|+\left|\psi_{n}\right|\leq M_{1}f_{n}+M_{2}g_{n}$$ for $n>n_{0}$. Now, taking the maximum of these two constants, i.e., $M:=\max\left\{ M_{1},M_{2}\right\}$, it follows that $$\left|\varphi_{n}+\psi_{n}\right|\leq M\left(f_{n}+g_{n}\right)$$ Thereby implying that $\varphi_{n}+\psi_{n}=\mathcal{O}\left(f_{n}\right)+\mathcal{O}\left(g_{n}\right)=\mathcal{O}\left(f_{n}+g_{n}\right)$.