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);     } 
  • 0
    This doesn't have any in$f$luence on the program, but your naming convention is bad.2012-06-16

1 Answers 1

5

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

  • 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.2012-06-16