You are correct to think that the equality $\sum^n_{i=0} O(1) =O(n)\,$ is not verified. Actually, if it has meaning at all, it may be contrived as verified, but not in the way you have in mind. For the equality to be meaningful, you must consider that the first $n$ is just a parameter that does not grow asymptotically, and that the second $n$ stands for the identity function $\lambda n.n$, which vould be a cleaner notation. With such assumptions, the equality would be correct if interpreted as inclusion (another problem in common uses of Landau notation), since $\sum^n_{i=0} O(1)= O(1) \subset O(n)$. But I suppose that is not what you intended, and that $n$ is supposed to grow asymptotically. Actually I tried to prove the equality wrong, but my problem was that I think it is meaningless, because the variable $n$ is not really supposed to be used in such definitions, and it appears only as a notational abuse, since $n$ is supposed to be asymptotically at infinity, with respect to the terms of the "finite" sum. I guess, what you mean by this notation is that a sum of $n$ functions that are each bounded by a constant when $n$ is sufficiently large will be bounded by $Kn$ for some constant $K$ when $n$ grows asymptotically to infinity.. This is not true, as the constants may grow arbitrarily. It is a problem of quantifier order. Take the following infinite sequence of functions: $$\forall i\geq 0 \; f_i(x)=i$$ These function are all constant, thus $$\forall i\geq 0 \; f_i\in O(1)$$ Then consider the function $$F(n)= \sum^n_{i=0}f_i(n)$$ You are tempted to say that since $\forall i\geq 0 \; f_i\in O(1)$, you then have $$F(n)\in \sum^n_{i=0}O(1) = (n+1)O(1) = O(n)$$ The argument $n$ of $F$ is supposed to be at infinity, since it is the same as the arguments of the $f_i$ that are replaced by their asymptotic limits. But then, it is also the upper bound for the sum, which is not at infinity. Actually you have simply $$F(n)= \sum^n_{i=0}i = \frac {n(n+1)} 2$$ Hence it is quite clear that $$F(n) \in O(n^2)$$. and more to the point that $$F(n) \notin O(n)$$. I can probably give a clearer explanation with time, but the main point is, you cannot use a variable that is already supposed to be at infinity. It is out of your reach :).