Is $n$ times $O(1)$ equivalent to $O(n)$? [duplicate]

Question

I am having a hard time figuring out if $$\sum^n_{i=0} O(1) =O(n)\,.$$

I think it doesn't but I am unable to find a convincing explanation for that, does anyone have an intuitive yet mathematical answer for that?

Answer 1

Think in terms of the definition: $f(m)=O(g(m))$ means that there exists some constants $c>0, M\ge 0$ such that $f(m) \le c\cdot g(m)$ for all $m\ge M$ so when you write $$ \sum_{i=1}^nO(1) $$ you mean that there are $n$ functions, $f_1, f_2, \dotsc, f_n$ and constants $c_1, c_2, \dotsc, c_n$ such that $f_i(m)\le c_i\cdot1$ for all sufficiently large values of $m$. Your sum then is $$ \sum_{i=1}^nO(1)=\sum_{i=1}^nf_i(m)\le \sum_{i=1}^nc_i\le \max_{1\le j\le n}\{c_j\}\cdot n $$ for all sufficiently large $m$. The problem here is, as Hendrik and babou pointed out, the $\max$ term is a function of $n$. For instance, if $f_i(m) = i$ were constant functions, individually they are all in $O(1)$ but their sum $$ F(n) = \sum_{i=1}^nf_i(m)= \sum_{i=1}^ni = \frac{n(n+1)}{2}\notin O(n) $$ The constants are not the only problem here, though, even if we restricted them all to be bounded by some constant $K$. Suppose we had defined the functions $f_i(m)$ to be $$ f_i(m) = \begin{cases} 2^i & \text{if $m<i$}\\ 1 & \text{if $m\ge i$} \end{cases} $$ Now each $f_i(m)\in O(1)$, since for each of them we could find a $c_i>0,M_i\ge 0$ such that for all $m\ge M_i$ we have $f_i(m)\le c\cdot 1$ (just pick $c_i=1$ and $M=i$ for instance).

In this case, we also don't have $F(n)\in O(n)$: even though all the $c_i = 1$ we can't now find a fixed N so that $F(n)\le Kn$ for all $n\ge N$, since we chose the functions $f_i$ so that the "crossing point", $M_i$, is a moving target. No matter what $N$ you pick, there will be a point where beyond $N$ the sum will be larger than $Kn$.

It seems that the best you can say is that $F(n)=O(n)$ when all of the $c_i$ are less than or equal to a single fixed bound and the same holds for all the $M_i$. Useful in some cases, I suppose, but woefully wrong in general.

Answer 2

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 :).