What is the sum of a sum?

Question

Σ from i=1 to n of(n)(n+1)/2

What is the upper limit of computation for a give n? is it O(n^3) O(n^2)?

Example:

n=1 , sum =1
n=2 , sum= 1+ 1+2 ,   sum = 4
n=3, sum= 1+1+2+1+2+3, sum = 10
n=4, sum = 1 + 1+2 + 1+2+3 + 1+2+3+4 = 20
n= 5, sum = 1+ 1+2 +1+2+3 +1+2+3+4 + 1+2+3+4+5 , sum = 35 
...
n=10,  sum = ..... , sum = 220 

etc, so what is the upper bound of this computation as a function of N? is it :

O(n^3)?

Answer 1

I presume that you mean Σ_{1 ≤ i ≤ n} i(i + 1)/2, since Σ_{1 ≤ i ≤ n} n(n + 1)/2 is just n²(n + 1)/2, which I'm sure you could have seen for yourself.

Anyway, why should you put up with mere asymptotic growth rates when you can compute the sum exactly?

Σ_{1 ≤ i ≤ n} i(i + 1)/2

= ½ Σ_{1 ≤ i ≤ n} (i² + i)

= ½ (n(n + 1)(2n + 1)/6 + n(n + 1)/2)

= n³/6 + n²/2 + n/3

The OEIS calls these numbers (1, 4, 10, 20, ...) the "tetrahedral numbers".

Answer 2

It is O(n^3).

To see that this is true you can visualize it as a triangular pyramid.

Answer 3

We can approximate n(n+1)/2 to n^2. So our sum is 1^2 + 2^2 + ... + n^2, and that is n(n+1)(2n+1)/6, which can be approximated to n^3. So the upper bound is n^3.

Answer 4

The exact formula for the sum is 1/6*n*(n+1)*(n+2), which is O(n^3).

Answer 5

Yes, summing some polynomial of degree d over k = 1,2,...,n yields a polynomial in n of degree d+1. Since k(k+1) / 2 is of degree 2 in k, its sum is of degree 2 + 1 = 3 in n.

Answer 6

Are you asking for computation complexity of the following sum, or for the big-O bound for the sum?

The second is O(n^3), like people already noticed, but to compute the sum you only need linear amount of additions and multiplications. You can regroup the summands and rewrite the sum as

n*1 + (n-1)*2 + ... + 1*n

from where it is clear that the sum can be computed in O(n).

Oh, and Gareth noted that there is closed-form expression for the sum, which computes in constant time.