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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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