Big O summation and additivity 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)$.
 A: 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
A: 
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.
A: 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.
