Refresh summation formulas

Question

I am trying to refresh on algorithm analysis. I am looking for a refresher on summation formulas.
E.g.
I can derive the $$\sum_{i = 0}^{N-1}i$$ to be N(N-1)/2 but I am rusty on the and more complex e.g. something like $$\sum_{i = 0}^{N-1}{\sum_{j = i+1}^{N-1}\sum_{k=j+1}^{N-1}}$$
Is there a good refresher material for this?
In my example my result of the inner most loop is:
$$N(N-1)(N-2)/2$$

which is wrong though

UPDATE
The sums I am describing are basically representing the following algorithm:

for (i = 0; i < n; i++) {  
   for( j = i+1; j < n; j++) {  
     for (k = j +1; j < n; j++) {  
      //code  
     }  
   }  
}  

This algorithm is O(N^3) according to all textbooks by definition of its structure. I am not sure why the answers are giving me an O(N^4)

Answer 1

Well, the basic time proven technique for simpler problems like this is guessing + proof by induction, something you can learn best by excercise. There certainly is way more advanced stuff even going into analytic number theory, but at least initially I would suggest you should get some problem book on induction or google a bit for excercises (there are hundreds around) and just start. This really helps to get some intuition, which I believe is really important to understand the more complex things.

If you want some literature instead, you should search for some books about discrete mathematics, there are several that are centered around computer science and should cover the topics you need. I've always been told that "Concrete Mathematics" by Graham, Knuth and Patashnik is a classic, but I haven't read it myself, so I won't guarantee anything.

Answer 2

For the problem in your post, I suppose that what you want to compute is $$\sum_{i = 0}^{N-1}{\sum_{j = i+1}^{N-1}\sum_{k=j+1}^{N-1}}k$$ For the most inner loop $$\sum_{k=j+1}^{N-1}k=\frac{1}{2} (N-j-1) (N+j)$$ So, for the middle loop $$\sum_{j=i+1}^{N-1}\frac{1}{2} (N-j-1) (N+j)=\frac{1}{6} (N-i-1) (N-i-2) (2 N+i)$$ and finally for the outer loop $$\sum_{i=0}^{N-1}\frac{1}{6} (N-i-1) (N-i-2) (2 N+i)=\frac{1}{24} (N-2) (N-1) N (3 N-1)$$ These results have been obtained using Faulhaber's formulas which give the sums of powers of positive integers. You must take into account the fact that, except the first one, the loops do not start at $0$ (this being particularly crucial for the most inner loop).

I hope and wish that I did not introduce any typo.

Concerning a refresher, I suggest you google "sums of powers of positive integers".

Answer 3

Here's a bit more detailed solution. Knowing the following three summations will help:

$$\sum_{i=0}^{N} i = \frac{N(N+1)}{2}$$

$$\sum_{i=0}^{N} i^2 = \frac{N(N+1)(2N+1)}{6}$$

$$\sum_{i=0}^{N} i^3 = \frac{N^2(N+1)^2}{4}$$

For the innermost sum:

$$\sum_{k=j+1}^{N-1}k = \sum_{k=0}^{N-1}k - \sum_{k=0}^{j}k = \frac{N(N-1)}{2} - \frac{j(j+1)}{2} = \frac{1}{2}(N(N-1) - j^2 + j)$$

For the middle sum:

\begin{align} \\ \sum_{j = i+1}^{N-1}\sum_{k=j+1}^{N-1}k &= \frac{1}{2}\sum_{j = i+1}^{N-1} (N(N-1) - j^2 + j) \\ &= \frac{1}{2}\left(N(N-1)(N-1-(i+1)+1) - \sum_{j = i+1}^{N-1}(j^2+j)\right) \\ &= \frac{1}{2}\left(N(N-1)(N-i-1) - \sum_{j = i+1}^{N-1}j^2 - \sum_{j = i+1}^{N-1}j\right)\\ &= \frac{1}{2}\left(N(N-1)^2 - N(N-1)i - \left(\sum_{j = 0}^{N-1}j^2 - \sum_{j = 0}^{i}j^2\right) - \left(\sum_{j = 0}^{N-1}j - \sum_{j = 0}^{i}j\right)\right)\\ &= \frac{1}{2}\left(N(N-1)^2 - N(N-1)i - \left(\frac{N(N-1)(2N-1)}{6} - \frac{i(i+1)(2i+1)}{6}\right) - \left(\frac{N(N-1)}{2} - \frac{i(i+1)}{2}\right)\right)\\ &= \frac{1}{12}\left(6N(N-1)^2 - N(N-1)(2N-1) - 3N(N-1) - 6N(N-1)i + i(i+1)(2i+1) + 3i(i+1)\right)\\ &= \frac{1}{12}\left(4N(N-1)(N-2) - 6N(N-1)i + 2i^3 + 6i^2 + 4i\right)\\ &= \frac{1}{6}\left(2N(N-1)(N-2) - 3N(N-1)i + i^3 + 3i^2 + 2i\right)\\ \end{align}

And finally the outermost sum:

\begin{align} \\ \sum_{i = 0}^{N-1}\sum_{j = i+1}^{N-1}\sum_{k=j+1}^{N-1}k &= \frac{1}{6}\sum_{i = 0}^{N-1}\left(2N(N-1)(N-2) - 3N(N-1)i + i^3 + 3i^2 + 2i\right)\\ \\ &= \frac{1}{6}\left(2N^2(N-1)(N-2) - 3N(N-1)\sum_{i = 0}^{N-1}i + \sum_{i = 0}^{N-1}i^3 + 3\sum_{i = 0}^{N-1}i^2 + 2\sum_{i = 0}^{N-1}i\right)\\ &= \frac{1}{6}\left(2N^2(N-1)(N-2) - 3N(N-1)\frac{N(N-1)}{2} + \frac{N^2(N-1)^2}{4} + 3\frac{N(N-1)(2N-1)}{6} + 2\frac{N(N-1)}{2}\right)\\ &= \frac{N(N-1)}{6}\left(2N(N-2) - \frac{3N(N-1)}{2} + \frac{N(N-1)}{4} + \frac{(2N-1)}{2} + 1\right)\\ &= \frac{N(N-1)}{24}\left(8N(N-2) - 6N(N-1) + N(N-1) + 2(2N-1) + 4\right)\\ &= \frac{N(N-1)}{24}(3N^2-7N+2)\\ &= \frac{N(N-1)(N-2)(3N-1)}{24}\\ \end{align}

Answer 4

The other answers are right, but they assume the innermost loop does work that is proportional to $k$, while I believe you intend it to be constant. You are right, the total work done is $O(N^3)$. You can use the sums-of-powers formulas mentioned to get the precise value if needed.

Answer 5

Based on your code, we can say that the possible codes inside the innermost loop executes in a constant time $A$. Then it's overall execution time can be approximated by: $$T_{N} = \sum_{i = 0}^{N-1}{\sum_{j = i+1}^{N-1}\sum_{k=j+1}^{N-1}}A$$

Using the summation properties given on Perry Iverson's answer, we can now solve.

Solving: \begin{align} \\ T_{N} &= \sum_{i = 0}^{N-1}{\sum_{j = i+1}^{N-1}\sum_{k=j+1}^{N-1}A} \\ &= A\sum_{i = 0}^{N-1}{\sum_{j = i+1}^{N-1}\sum_{k=j+1}^{N-1}1} \\ &= A\sum_{i = 0}^{N-1}{\sum_{j = i+1}^{N-1}[(N-1) - (j+1) + 1]} \\ &= A\sum_{i = 0}^{N-1}{\sum_{j = i+1}^{N-1}[(N-1) - j]} \\ &= A\sum_{i = 0}^{N-1}\left(\sum_{j = i+1}^{N-1}(N-1) - \sum_{j = i+1}^{N-1}j\right) \\ &= A\sum_{i = 0}^{N-1}\left((N-1)\sum_{j = i+1}^{N-1}1 - \dfrac{1}{2}[N(N-1)-i(i+1)]\right) \\ &= A\sum_{i = 0}^{N-1}\left((N-1)(N-1-i) - \dfrac{1}{2}[N(N-1)-i(i+1)]\right) \\ &= A\sum_{i = 0}^{N-1}\left(\dfrac{1}{2}(N-1)(N-1)+\dfrac{1}{2}i^2+i(\dfrac{3}{2}-N)\right) \\ &= \dfrac{A}{2}\sum_{i = 0}^{N-1}\left((N-1)(N-2)+i(2N-3)+i^2\right) \\ &= \dfrac{A}{2}\left((N-1)(N-2)\sum_{i = 0}^{N-1}1+(2N-3)\sum_{i = 0}^{N-1}i+\sum_{i = 0}^{N-1}i^2\right) \\ &= \dfrac{A}{2}\left((N-1)(N-2)N+(2N-3)\dfrac{N(N-1)}{2}+\dfrac{N(N-1)(N-2)}{6}\right) \\ &= \dfrac{AN(N-1)(N-2)}{6} \end{align}

To check it, try running this program:

int getNumLoop(int p_num){

    int sum = 0;
    for(int i = 0; i < p_num; ++i)
    for(int j=i+1; j < p_num; ++j)
    for(int k=j+1; k < p_num; ++k)
    {
        sum++;
    }

    return sum;
}

int computeNumLoop(int p_num){

    return p_num*(p_num-1)*(p_num-2)/6;

}

void main(){

    for(int N = 0; N < 10; ++N){
        printf("N = %d: loop[%d], compute[%d]", N, getNumLoop(N), computeNumLoop(N));
    }

}

Update:

I found out that this is just $A{ N \choose 3}$

If you increase the number of loop, say 5, the result will be $A{ N \choose 5}$.

In general, the total execution time of this kind of loop structure is $A{ N \choose k}$, where $k$ is the number of loop.