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

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?

-
I can't believe there's a "questions" tag. –  Marcelo Cantos Aug 3 '10 at 10:47
Is this homework? It looks an awful lot like homework. –  Marcelo Cantos Aug 3 '10 at 10:48
@Marcelo Cantos: Well, I can spot two ;) –  Felix Kling Aug 3 '10 at 10:48
@Felix Kling: Ah, of course. But did they press the "Ask Questions" button? –  Marcelo Cantos Aug 3 '10 at 10:50
Trying to work this out makes my brain hurt. –  fearofawhackplanet Aug 3 '10 at 10:50
show 1 more comment

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

-
if we cut the first loop into 2 symetrical (stoping and starting a n/2) we can rewrite the nested loop to stop a n/2 so results becomes (when each loop stop a the previous one -1) 2*C(n/2, for_loops) , If I am right. –  mb14 Aug 3 '10 at 11:26

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

-
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://stackoverflow.com/questions/3395726/how-to-calculate-total-no-of-iteration-of-innermost-loop-of-nested-for-loop-is?answertab=oldest", "fetch_time": 1394710342000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2014-10/segments/1394678666156/warc/CC-MAIN-20140313024426-00042-ip-10-183-142-35.ec2.internal.warc.gz", "warc_record_offset": 138859036, "warc_record_length": 16719, "token_count": 881, "char_count": 2591, "score": 3.6875, "int_score": 4, "crawl": "CC-MAIN-2014-10", "snapshot_type": "latest", "language": "en", "language_score": 0.7842476963996887, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00000-of-00064.parquet"}