how to calculate total no of iteration of innermost loop of nested for loop? is there any formula?

Question

for example

int count=0
for(int i=0;i<12;i++)
   for(int j=i+1;j<10;j++)
       for(int k=j+1;k<8;k++)
           count++;
System.out.println("count = "+count);

or

for(int i=0;i<I;i++)
   for(int j=i+1;j<J;j++)
       for(int k=j+1;k<K;k++)
        :       
        :
        :
        for(int z=y+1;z,<Z;z,++,)
         count++;

what is value of count after all iteration? Is there any formula to calculate it?

Answer 1

Not a full answer but when i, j and k are all the same (say they're all n) the formula is C(n, nb_for_loops), which may already interest you :)

    final int n = 50;
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                for (int l = k+1; l < n; l++) {
                    count++;
                }
            }
        }
    }
    System.out.println( count );

Will give 230300 which is C(50,4).

You can compute this easily using the binomail coefficient:

http://en.wikipedia.org/wiki/Binomial_coefficient

One formula to compute this is: n! / (k! * (n-k)!)

For example if you want to know how many different sets of 5 cards can be taken out of a 52 cards deck, you can either use 5 nested loops or use the formula above, they'll both give: 2 598 960

Answer 2

It's a math problem of summation

Basically, one can prove that:

for (i=a; i<b; i++) 
    count+=1 

is equivalent to

count+=b-a

Similarly,

for (i=a; i<b; i++) 
    count+=i 

is equivalent to

count+= 0.5 * (b*(b+1) - a*(a+1))

You can get similar formulas using for instance wolframalpha (Wolfram's Mathematica)

This system will do the symbolic calculation for you, so for instance,

for(int i=0;i<A;i++)
   for(int j=i+1;j<B;j++)
      for(int k=j+1;k<C;k++)
          count++

is a Mathematica query:

http://www.wolframalpha.com/input/?i=Sum[Sum[Sum[1,{k,j%2B1,C-1}],{j,i%2B1,B-1}],{i,0,A-1}]

Answer 3

That's roughly the volume of an hyperpyramid http://www.physicsinsights.org/pyramids-1.html => 1/d * (n ^d) (with d dimension)

The formula works for real number so you have to adapt it for integer (for the case d=2 (the hyperpyramid is a triangle then) , 1/2*(n*n) becomes the well know formula n(n+1)/2 (or n(n-1)/2) depending if you include the diagonal or not). I let you do the math

I think the fact your not using n all time but I,J,K is not a problem as you can rewrite each loop as 2 loop stopping in the middle so they all stop as the same number

the formula might becomes 1/d*((n/2)^d)*2 (I'm not sure, but something similar should be ok)

That's not really the answer to your question but I hope that will help to find a real one.