# What is the sum of this?

What is the sum of this

$$\{n,n-1,...,3,2,1\}, ...... \{5,4,3,2,1\}, \{4,3,2,1\}, \{3,2,1\}, \{2,1\}, \{1\}$$

I am learning Data Structures and Algorithms now, I want to calculate the time-complexity of a nested loop. I suspect there is term and formula for this pattern.

    static int count = 0;

//time complexity of this nested loop
public static void run(int n) {
for (int i = 1; i * i < n; i++) {
for (int j = i; j * j < n; j++) {
for (int k = j; k * k < n; k++) {
System.out.println(++count);
}
}
}
}

public static void cal(int n) {
int total = 0;
int temp = (int) Math.pow(n, 0.5);
for (int i = temp; i > 0; i--) {
total += i * (i + 1) / 2;
}
System.out.println(total);
}

public static void main(String[] args) {
run(12345);
cal(12345);
}

• This doesn't have any influence on the program, but your naming convention is bad. – Norbert Jun 16 '12 at 17:59

Each of the sums separately is $\sum_{j=1}^k j = \frac{1}{2}k^2 + \frac{1}{2}k$.
In addition, $\sum_{k=1}^n k^2 = \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n$,
The total sum is then $$\sum_{k=1}^n \sum_{j=1}^k j = \sum_{k=1}^n (\frac{1}{2}k^2 + \frac{1}{2}k) = \frac{1}{2}\sum_{k=1}^n k^2 + \frac{1}{2} \sum_{k=1}^n k = \frac{1}{6} n^3 + \frac{1}{2} n^2 + \frac{1}{3} n = \frac{n(n+1)(n+2)}{6}$$
• Note that this is just $n+2\choose3$. In general, the sum of $n\choose k$ from $n=1$ to $m$ is $m+1 \choose k+1$, by a simple counting argument. – Erick Wong Jun 16 '12 at 18:02