0
$\begingroup$

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);
    }
$\endgroup$
1
  • $\begingroup$ This doesn't have any influence on the program, but your naming convention is bad. $\endgroup$
    – Norbert
    Jun 16, 2012 at 17:59

1 Answer 1

5
$\begingroup$

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

$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$
    – Erick Wong
    Jun 16, 2012 at 18:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .