# Number of Iterations

Printable View

• September 15th 2010, 02:49 PM
aarnold
Number of Iterations
How many times does the innermost loop execute:

Code:

for k = 1 to n
for j = 1 to k
for i = 1 to j
#the inner loop
end for
end for
end for

I did the first few by hand to see if I noticed anything.

Looking at Pascal's triangle I saw the numbers appear in the diagonal. Eventually I came up with the answer:

(n + 2) choose (n - 1)

But I don't know how I got there. Does this have anything to do with the Principle of Inclusion and Exclusion?
• September 15th 2010, 03:16 PM
yeKciM
Quote:

Originally Posted by aarnold
How many times does the innermost loop execute:

Code:

for k = 1 to n
for j = 1 to k
for i = 1 to j
#the inner loop
end for
end for
end for

I did the first few by hand to see if I noticed anything.

Looking at Pascal's triangle I saw the numbers appear in the diagonal. Eventually I came up with the answer:

(n + 2) choose (n - 1)

But I don't know how I got there. Does this have anything to do with the Principle of Inclusion and Exclusion?

that can't be (n+2) or (n-1) iterations in that loop with "i" :D:D:D

i have question for you :D why don't compile this ? and is it ( k=1 ; k<= n or you need k<n ; k++ )

for n=2 there are 6 , for n=3 there is 18 , for n=4 there is 40 ... repetitions :D

lol for n = 50 there is 63 750 of executions of that loop :D
• September 15th 2010, 03:39 PM
aarnold
Hi, I'm assuming that I am calculating for k <= n.

A quick check with python gives the following results:

Code:

>>> def iterate(n):
c = 0
for k in range(1, n + 1):
for j in range(1, k + 1):
for i in range(1, j + 1):
c = c + 1
print c

>>> iterate(1)
1
>>> iterate(2)
4
>>> iterate(3)
10
>>> iterate(4)
20
>>> iterate(5)
35
>>> iterate(6)
56

and here's Pascal's triangle:

Code:

1
1    1
1    2    1
1  3  3  1
1  4  6  4  1
1  5  10  10  5  1
1  6  15 20  15 6 1

If the row and column's are 0-based, look at the n+2 row and the n-1 column and you get the number of iterations.

So if n = 1, look at row 3, column 0: 1
n = 2, look at row 4, column 1: 4
n = 3, row 5, column 2: 10

etc.

I determined this to be (n+2) choose (n-1).

However, I don't think this is a mathematical enough answer.
• September 15th 2010, 04:00 PM
yeKciM
hm...

Code:

cin>> n ;
int iter = 0 ;
for (int k = 1 ; k<= n ; k++ ) {
for( int j= 1 ; j <= k ; j++ ) {
for( int i =1 ; i< =j i ++ ) {
iter++ ;
cout << << "No." << iter << "." << i << endl;
}
}
}

and get totally something else :D
• September 15th 2010, 04:16 PM
undefined
Quote:

Originally Posted by aarnold
How many times does the innermost loop execute:

Code:

for k = 1 to n
for j = 1 to k
for i = 1 to j
#the inner loop
end for
end for
end for

I did the first few by hand to see if I noticed anything.

Looking at Pascal's triangle I saw the numbers appear in the diagonal. Eventually I came up with the answer:

(n + 2) choose (n - 1)

But I don't know how I got there. Does this have anything to do with the Principle of Inclusion and Exclusion?

$1+2+3+...+n = t_n =$ nth triangle number $=\binom{n+1}{2}$

$<br /> t_1 + t_2 + t_3 + ... + t_n =$ nth tetrahedral number $=\binom{n+2}{3}$

The pattern continues. Notice that n+2-3 = n-1. (Combine this with the knowledge that $\binom{n}{k}=\binom{n}{n-k}$.)

You can justify the triangular number formula by considering the handshake problem; given a group of n people, if everyone shakes everyone else's hand, how many handshakes took place? So the first person shakes n-1 hands. Add to that n-2 for the second person -- because if you added n-1 you would re-count the handshake with the first person. So you get (n-1) + n + ... + 1, which is the (n-1)st triangle number.

We can generalize as follows: Consider a set of n points, n > 2, such that no three points are collinear. How many triangles can we form by choosing vertices from these n points? Start with one point, and ask how many triangles can form with it. You get the (n-2)nd triangle number. (Because you are choosing any two points out of the n-1 remaining points, which is a problem we just solved above.) For the next point you get the (n-3)rd triangle number, etc.

There may be a cleaner way to state it, but that at least does the job.
• September 16th 2010, 05:23 AM
CaptainBlack
Quote:

Originally Posted by aarnold
How many times does the innermost loop execute:

Code:

for k = 1 to n
for j = 1 to k
for i = 1 to j
#the inner loop
end for
end for
end for

I did the first few by hand to see if I noticed anything.

Looking at Pascal's triangle I saw the numbers appear in the diagonal. Eventually I came up with the answer:

(n + 2) choose (n - 1)

But I don't know how I got there. Does this have anything to do with the Principle of Inclusion and Exclusion?

For any value of $$$ j$ the inner loop executes $$$ j$ times.

For any value of $$$ k$ the inner look executes $\sum_{j=1}^k j$

So the total number of executions of the inner code is $\sum_{k=1}^n \left[\sum_{j=1}^k j\right]$

With a bit of jiggery-pokery this becomes: $\dfrac{n(n+1)(n+2)}{6}$

CB
• September 16th 2010, 06:54 AM
MathoMan
Here's that jiggery-pokery stuff:
$\sum_{k=1}^n \left[\sum_{j=1}^k j\right]=\sum_{k=1}^n\frac{k(k+1)}{2}=$ $=\frac{1}{2}\left(\sum_{k=1}^n k^2+\sum_{k=1}^n k\right)=\frac{1}{2}\left(\frac{n(n+1)(2n+1)}{6}+\ frac{n(n+1)}{2}\right)=\dfrac{n(n+1)(n+2)}{6}$
All times are GMT -8. The time now is 03:26 PM.
{"extraction_info": {"found_math": true, "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": 13, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9528090953826904, "perplexity_flag": "middle"}