Order of Natural Numbers in Algorithms

Question

Could anyone describe, why this is a True statements?

if $f_i$ be a function of natural numbers to natural numbers and $f_i(n)=O(n)$ then $\Sigma_{i=1}^{n} f_i(n)=O(n^2) $

Answer 1

The statement is false as written. Suppose that each $f_{i}(n)$ satisfies $i^2 n \leq f_{i}(n)\leq 2 i^{2}n$. Then it is the case that $f_{i}(n)=O(n)$ (you can take the constant for $f_{i}(n)$ to be $2i^2$). Then, your function $f$ is lower-bounded by $\sum_{i=1}^{n} i^2 n \leq \sum_{i=1}^{n}f_{i}(n)$ and $\sum_{i=1}^{n}i^2 n \sim n^3$.

In order for the statement to be true, you need each $f_{i}(n)$ to be $O(n)$ using one constant for all of them, i.e. $f_{i}(n)\leq Cn$ for all $i$.

EDIT: and, you need the bound to be true for all $n\geq N$ (where the same $N$ works for each $f_{i}$).

Answer 2

Since you are summing from 1 to n, over a function that already is $O(n)$, you're taking the function $n$ times for every number between $1$ and $n$. This should pop out to you as $n\cdot n = n^2$.

Answer 3

For every $i$, there is an $N_i$ and a $C_i$ such that for all $n\ge N_i$, $f_i(n)\le C_in$.

Then, taking $N=\max_iN_i$ and $C=\max_iC_i$, for all $n\ge N$, $\sum_if_i\le \sum_iCn=Cn^2$.

This reasoning does not hold if the $N_i$ or $C_i$ are unbounded.