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

  • $\begingroup$ 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$. $\endgroup$ – automaton 3 Sep 28 '13 at 8:06

You can definitely use the method used to prove O(f(n)) + O(g(n)) = O(f(n) + g(n)) to show what you want. But, you must also add the condition that f(n) and g(n) are greater than zero. I will prove this for you and leave it you to see how to apply it to the problem you presented.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.