Summation of $O(n)$ from $1\le k\le n$

Summation of $O(n)$ from $1\le k\le n$.

I think it should be $O(n)$ only. Because we are addition $O(k)$ and maximum order will be $O(n)$. But answer is given as $O(n^2)$.

Correct me if I'm wrong.

-
What if instead of $O(n)$, we had just plain $n$? Isn't $\sum_{k=1}^n n = n^2$? – Dilip Sarwate Dec 17 '12 at 22:40
$\mathcal O (n^2)$ is correct asymptotic for this summation. It's bacasue Big-Oh is upper bound for some function. – Bartosz Przybylski Dec 17 '12 at 22:44
suppose there are 3 function in a program and time complexity of first is O(1) , for second O(logn), and for third O(n+10000) than what would be resultant Time Complexity of whole program?? isn't O(n) – user1771809 Dec 17 '12 at 22:50
Where is $k$ in the summation? – Paresh Dec 17 '12 at 23:31
@Paresh. k=3 here – user1771809 Dec 18 '12 at 13:59

3 Answers

I think I understood you from your comments above. I think you have issues in the very basics of complexity analysis.

I think what you want to say is that you are summing the term $O(n)$, $O(k)$ times for $1 \leq k \leq n$ . right? In this case, the answer is $O(nk)$.

If $O(k) \in O(n)$ (for example $k = n/c$ for $c \in O(1)$) then, then the answer is $O(n^2)$. is that what you want ?

Comment I see from the comments $k = 3$. Therefore, I can understand $k$ is constant and $O(k) \in O(1)$. Therefore $O(kn) \in O(n)$. This is why you get $O(n)$, while you are confused with $O(n^2)$. But for instance, if k = n * (some weird constants) = 3, then badly your solution is $O(n^2)$.

Example: Assume that your program requires $k$ functions, each of with requires $O(1)$ (that is, no matter what size of input you got (i.e. $n$) it will always take $O(1)$ time units to run a function). In this case, your total is $O(k)$. The number of functions in your program also does not depend on the number of $n$. It is also constant (that is, $O(1)$). Therefore, the total running time of your program is $O(1)$ !

If the functions above required $O(n)$ execution time complexity, then similarly it is $O(n)$.. This is all because $k$ is constant. Even if $k = 10^6$ and your input was of size $n = 100$. The same bound remains. Why ? because one day, you will run an input of size $n = 10^{1000}$, but $k$ remains to be $10^6$.

One example commonly found. Assume we have a graph $G = (V, E)$ constructed in a way such that each vertex $v$ is connected to $d$ other vertices. In this case $0 \leq d \leq n - 1$. Therefore, the number of edges of the graph $|E| = (\sum _{v \in V} d) / 2 = nd /2$. If $d$ is fixed (let's say to exactly 4), then $|E| \in O(n)$.

However, assume that $d$ is a function of $n$. For instance, a vertex $v$ select $1/2$ of the other vertices as neighbors. Therefore, $d = \frac{1}{2}(n-1)$. In this case $|E| = nd/2 = n (\frac{1}{2}(n-1)) \in O(n^2)$.

In the first case (i.e. $|E| \in O(n)$), the graph is sparse. In the other case, the graph is dense.

-
thanks a lot my doubt is clear now! means if our program consists of thousands of functions than we choose highest degree time complexity function as overall time complexity of program because the numbers of functions is constant here. but when program is consists of n(very large number of functions) than the case is different and we can not ignore. am i right? – user1771809 Dec 19 '12 at 9:57

Suppose $T_n = O(n)$. That means that for some constant $C$, $T_n \leq Cn$. Therefore $$\sum_{m=1}^n T_m \leq C \sum_{m=1}^n m = \frac{C}{2} m(m+1) = O(m^2).$$ If also $T_n = \Omega(n)$ then you can show in exactly the same way that the sum is $\Omega(n^2)$, so that no better bound is possible (for concreteness, you can take $T_n = n$).

-
its creating confusion to me when i am seeing it in programming convention as i mentioned above. please clearify my doubt.. – user1771809 Dec 18 '12 at 14:03
When you're adding a constant number of big-O terms, then the result is the maximal big-O term. You can try to prove that using the definition of big-O. – Yuval Filmus Dec 18 '12 at 17:40
i am just taking an example. e.g. O(1), O(logn),O(nlogn),O(n^2) are complexities of functions in a program. then summation of all these complexities will be maximum of all i.e. O(n^2). and the complexity of program will be O(n^2). correct me? – user1771809 Dec 18 '12 at 21:21
That's correct. – Yuval Filmus Dec 18 '12 at 21:24
than why not O(1)+O(2)+O(3)+O(4)+............O(n)=O(n) only? – user1771809 Dec 18 '12 at 22:43

There's no correct answer unless you specify what the $n$ functions are.

For example, consider, for each $k$, the function $f_k(n) = kn$. For any fixed $k$, $f_k(n) \in O(n)$.

Yet $\sum_{k=1}^{n} f_k(n) = \sum_{k=1}^n kn = n\frac{n(n+1)}{2} \in O(n^3)$. A different choice of sequence $f_k$ could yield just about any function in $\Omega(n)$.

So we can take a sequence of $k$ functions, each of which is $O(n)$, and sum them to get a function that's $O(n^3)$ (for instance).

If you have a single fixed function $f(n) \in O(n)$, then of course $\sum_{k=1}^n f(n) = nf(n) \in O(n^2)$.

-