Big O summation and additivity

Question

I'm not sure whether the following equality is correct, or rather, whether my interpretation of it is correct: $$\sum_{i=0}^n O(f(i)) = O(\sum_{i=0}^n f(i)) \qquad (1)$$

The way I interpret the LHS is that $i$ is a function of $n$ and each $f(i)$ becomes essentially a function of n $f(i) = f(i(n))$, so now I am summing a bunch of functions in n and invoke the property: $$O(f(n)) + O(g(n)) = O(f(n) + g(n))$$ Assuming all functions are positive. This also implies a change of variables; i.e., $O$ on RHS is with respect to $n$. Feels kinda wonky frankly.

Edit:

Here is one transformation from a book that made me think that (1) is a thing (ofc I don't know what their actual reasoning was 'cause they didn't provide any step by step solution):

$$\sum_{i=0}^{\lfloor{logn}\rfloor}(\lceil{n\over2^{i+1}}\rceil O(i)) = O(n\sum_{i=0}^{\lfloor{logn}\rfloor}{i\over2^{i+1}}) \qquad (2)$$

Assuming I reduce the summation on the LHS to: $$\sum_{i=0}^{\lfloor{logn}\rfloor}O({ni\over2^{i+1}})$$

Then I end up with (1).. As far as I understand, the line of reasoning that produced the LHS of (2) was you loop over $logn$ some levels of a complete binary tree, and on each height $i$ you have max $\lceil{n\over2^{i+1}}\rceil$ nodes, and on each you invoke a function that runs in $O(i)$.

Answer 1

Alright, I did some research (should have done before I asked..). The above equality (1) out of context is meaningless. It seems that the convention is that: $$\sum_{i=0}^n O(f(i)) := \sum_{i=0}^n g(i) \qquad ,g(x) = O(f(x))$$ Where a all g's have the same constant. Then sometimes the above equality (1) appears to be "true":

$$\sum_{i=0}^{\lfloor{logn}\rfloor}\lceil{n\over2^{i+1}}\rceil O(i) = \sum_{i=0}^{\lfloor{logn}\rfloor}\lceil{n\over2^{i+1}}\rceil g(i) ,g(x) =O(x)$$

Then $\forall n > n_0$

$$\sum_{i=0}^{\lfloor{logn}\rfloor}\lceil{n\over2^{i+1}}\rceil g(i) \le \sum_{i=0}^{\lfloor{logn}\rfloor}\lceil{n\over2^{i+1}}\rceil ci = {c\over2}n\sum_{i=0}^{\lfloor{logn}\rfloor}\lceil{i\over2^i}\rceil = O(n\sum_{i=0}^{\lfloor{logn}\rfloor}{i\over2^i})$$

Relevant link: https://cs.stackexchange.com/questions/63184/how-does-o-transform-this-sum-like-that?noredirect=1&lq=1

Answer 2

In the left-hand side

$$\sum_{i=0}^n O(f(i)),$$

the arguments of the $O$ terms are constants (they do not depend on $n$) so that the notation $$O(f(i))$$ is essentially meaningless.

E.g. let use take $f(i):= i^2$. Then

$$O(0)+O(1)+O(4)+O(9)+\cdots O(n^2)$$ is absurd.

Answer 3

We assume $f$ is a non-negative function and consider \begin{align*} \sum_{i=0}^n O(f(i)) = O\left(\sum_{i=0}^n f(i)\right)\qquad\qquad n\geq 0\tag{1} \end{align*}

The left-hand side of (1) has the following meaning:

• The expression $O(f(i))$ stands for the set of all two-variable functions of the form $g(f(i),n)$ such that there exists a constant $C>0$ with $|g(f(i),n)|\leq Cf(i)$ for $0\leq i\leq n$.

• The sum of this set of functions, for $0\leq i\leq n$, is the set of all functions $h(n)$ of the form \begin{align*} h(n)&=\sum_{i=0}^ng(f(i),n)\\ &=g(f(0),n)+g(f(1),n)+\cdots g(f(n),n)\tag{2} \end{align*}

We obtain \begin{align*} \left|\sum_{i=0}^ng(f(i),n)\right|&\leq \left|\sum_{i=0}^nCf(i)\right|\\ &=C\sum_{i=0}^nf(i) \end{align*}

It follows all such functions $h(n)$ belong to the right-hand side of (1); therefore (1) is true.

The meaning of the left-hand side of (1) is stated in section 9.2 $O$ Notation of Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik. A corresponding sum is given as (9.16).

We are now ready to calculate \begin{align*} \sum_{i=0}^{\left\lfloor \log_2 n\right\rfloor}\left(\left\lceil\frac{n}{2^{i+1}}\right\rceil O(i)\right) =O\left(n\sum_{i=0}^{\left\lfloor \log_2 n\right\rfloor}\frac{i}{2^{i+1}}\right)\tag{2} \end{align*} We use for convenient calculation $\log_2$ as upper limit of the sum.

• The summand at the left-hand side of (2) stands for the set of all two-variable functions of the form $\left\lceil\frac{n}{2^{i+1}}\right\rceil f(i,n)$ such that there exists a constant $C>0$ with $|f(i,n)|\leq C\cdot i$ for $0\leq i\leq n$.

• The sum of this set of functions, for $0\leq i\leq n$, is the set of all functions $g(n)$ of the form \begin{align*} g(n)=\sum_{i=0}^{\left\lfloor \log_2 n\right\rfloor}\left\lceil\frac{n}{2^{i+1}}\right\rceil f(i,n)\tag{3} \end{align*}

We obtain \begin{align*} \left|\sum_{i=0}^{\left\lfloor \log_2 n\right\rfloor}\left\lceil\frac{n}{2^{i+1}}\right\rceil f(i,n)\right| &\leq \left|\sum_{i=0}^{\left\lfloor \log_2 n\right\rfloor}\left\lceil\frac{n}{2^{i+1}}\right\rceil C\cdot i\right|\\ &= C\left|\sum_{i=0}^{\left\lfloor \log_2 n\right\rfloor}\left\lceil\frac{n}{2^{i+1}}\right\rceil i\right|\\ &\leq 2C n\sum_{i=0}^{\left\lfloor \log_2 n\right\rfloor}\frac{i}{2^{i+1}}\tag{4} \end{align*}

It follows all such functions $g(n)$ belong to the right-hand side of (2) and the claim (2) follows.

Comment: In (4) we use that $\frac{n}{2^{i+1}}\geq \frac{1}{2}$ if $0\leq i\leq\left\lfloor \log_2 n\right\rfloor$, so that we can use a factor $2$ to get an upper bound.