Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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);
    }
share|improve this question
    
This doesn't have any influence on the program, but your naming convention is bad. –  no identity Jun 16 '12 at 17:59

1 Answer 1

up vote 5 down vote accepted

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$,

both of which can be proved by induction.

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}$$

share|improve this answer
4  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.