1
$\begingroup$

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)

$\endgroup$
2
  • $\begingroup$ The algorithm is fishy, both inner loops increment j and k isn't $\endgroup$
    – vonbrand
    Commented Jun 15, 2014 at 11:19
  • $\begingroup$ That's because you assumed that the counter variable k is in the innermost sum. It should be a constant only. $\endgroup$
    – acegs
    Commented Feb 15, 2015 at 2:18

5 Answers 5

2
$\begingroup$

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}

$\endgroup$
2
  • $\begingroup$ The result of your answer is O(N^4) while three nested loops are always O(N^3). Something is wrong here. Am I messing up something in my OP? $\endgroup$
    – Jim
    Commented Jun 14, 2014 at 22:41
  • 1
    $\begingroup$ @Jim notice that with one loop $\sum_{i=0}^{N} i = O(N^2)$, this is because the sum is over $i$, rather than a constant. The sum $\sum_{i=0}^{N-1} \sum_{j=i+1}^{N-1} \sum_{k=j+1}^{N-1} 1 = O(N^3)$. $\endgroup$ Commented Jun 16, 2014 at 1:11
1
$\begingroup$

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".

$\endgroup$
7
  • $\begingroup$ But the outer loop is executed N times. According to your answer the outer loop is executed N^3 times. $\endgroup$
    – Jim
    Commented Jun 14, 2014 at 14:09
  • $\begingroup$ No. You have three embedded loops si it is more or less $N^3$ and you have to sum; this leads to $N^4$ as a result. $\endgroup$ Commented Jun 14, 2014 at 14:13
  • $\begingroup$ I am confused now. I always knew that 3 nested for loops is O(N^3). The outer loop is executed N-1 times and the inner loop is executed N(N-1)/2 times because I verified plugin in small numbers and N(N-1)/2 gives the correct result. I could not derive the inner-inner most loop. So now I am lost with the N^4 answer $\endgroup$
    – Jim
    Commented Jun 14, 2014 at 14:15
  • $\begingroup$ Because the innermost loop contains k, which is the index variable of the sum. That will be the sum of increasing numbers up to N-1 so it is N^2 to the innermost loop only. That's where the excess N come from. If it's a constant and not an index variable of the summations, you'll get 3 Ns only. $\endgroup$
    – acegs
    Commented Jun 14, 2014 at 19:22
  • $\begingroup$ The result of your answer is O(N^4) while three nested loops are always O(N^3). Something is wrong here. Am I messing up something in my OP? $\endgroup$
    – Jim
    Commented Jun 14, 2014 at 22:41
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ What about the particular example I am stuck on? $\endgroup$
    – Jim
    Commented Jun 14, 2014 at 12:37
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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