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".