Ytukyg

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{nover2^{i+1}}rceil O(i)) = O(nsum_{i=0}^{lfloor{logn}rfloor}{iover2^{i+1}}) qquad (2)$$

Assuming I reduce the summation on the LHS to:
$$sum_{i=0}^{lfloor{logn}rfloor}O({niover2^{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{nover2^{i+1}}rceil$ nodes, and on each you invoke a function that runs in $O(i)$.

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.

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{nover2^{i+1}}rceil O(i) = sum_{i=0}^{lfloor{logn}rfloor}lceil{nover2^{i+1}}rceil g(i) ,g(x) =O(x)$$

Then $forall n > n_0$

$$sum_{i=0}^{lfloor{logn}rfloor}lceil{nover2^{i+1}}rceil g(i) le sum_{i=0}^{lfloor{logn}rfloor}lceil{nover2^{i+1}}rceil ci = {cover2}nsum_{i=0}^{lfloor{logn}rfloor}lceil{iover2^i}rceil = O(nsum_{i=0}^{lfloor{logn}rfloor}{iover2^i})$$

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

We assume $f$ is a non-negative function and consider
begin{align*}
sum_{i=0}^n O(f(i)) = Oleft(sum_{i=0}^n f(i)right)qquadqquad ngeq 0tag{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 $0leq ileq n$.




• The sum of this set of functions, for $0leq ileq 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|\
&=Csum_{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}^{leftlfloor log_2 nrightrfloor}left(leftlceilfrac{n}{2^{i+1}}rightrceil O(i)right)
=Oleft(nsum_{i=0}^{leftlfloor log_2 nrightrfloor}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 $leftlceilfrac{n}{2^{i+1}}rightrceil f(i,n)$ such that there exists a constant $C>0$ with $|f(i,n)|leq Ccdot i$ for $0leq ileq n$.




• The sum of this set of functions, for $0leq ileq n$, is the set of all functions $g(n)$ of the form
  begin{align*}
  g(n)=sum_{i=0}^{leftlfloor log_2 nrightrfloor}leftlceilfrac{n}{2^{i+1}}rightrceil f(i,n)tag{3}
  end{align*}

We obtain
begin{align*}
left|sum_{i=0}^{leftlfloor log_2 nrightrfloor}leftlceilfrac{n}{2^{i+1}}rightrceil f(i,n)right|
&leq left|sum_{i=0}^{leftlfloor log_2 nrightrfloor}leftlceilfrac{n}{2^{i+1}}rightrceil Ccdot iright|\
&= Cleft|sum_{i=0}^{leftlfloor log_2 nrightrfloor}leftlceilfrac{n}{2^{i+1}}rightrceil iright|\
&leq 2C nsum_{i=0}^{leftlfloor log_2 nrightrfloor}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 $0leq ileqleftlfloor log_2 nrightrfloor$, so that we can use a factor $2$ to get an upper bound.