Understanding how much time nested loops will take

Question

I am trying to understand how many times the instruction "x = x + 1" is executed in the code below, like the function "n":

for (i=1; i<=n; i++) for (j=1; j<=i; j++) for (k=1; k<=j; k++) x = x + 1 ; 

If I'm not mistaken, the first cycle is executed n times, and the second - n (n + 1) / 2 times, but in the third cycle I get lost. That is, I can calculate how many times it will be executed, but I can not find the formula or explain it mathematically.

You can?

By the way, this is not homework or anything else. I just found in a book and thought it was an interesting concept to study.

Answer 1

Consider a for (i=1; i <= n; i++) loop for (i=1; i <= n; i++) . It is trivial to see that it loops n times. We can do it like:

 * * * * * 

Now that you have two nested loops, your inner loop will loop n (n + 1) / 2 times. Notice how this forms a triangle, and in fact, numbers of this shape are known as triangular numbers .

 * * * * * * * * * * * * * * * 

So, if we extend this to another dimension, it forms a tetrahedron. Since I cannot do 3D here, imagine that each of these layers is stacked on top of each other.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 

They are called tetrahedral numbers , which are generated by this formula:

 n(n+1)(n+2) ----------- 6 

You should be able to confirm that this is indeed the case with a small test program.

If we notice that 6 = 3 !, it’s not so difficult to see how this template generalizes to higher sizes :

 n(n+1)(n+2)...(n+r-1) --------------------- r! 

Here r is the number of nested loops.

Answer 2

The mathematical formula is here .

This is O (n ^ 3) complexity.

Answer 3

This number is equal to the number of triples {a, b, c}, where a <= b <= c <= n.
Therefore, it can be expressed as a combination with repetitions. . In this case, the total number of combinations with repetitions is: n (n + 1) (n + 2) / 6

Answer 4

The third inner loop is the same as the second inner loop, but your n is a formula.

So, if your outer loop is n times ...

and your second loop n(n+1)/2 times ...

your third cycle ...

(n(n+1)/2)((n(n+1)/2)+1)/2

It is rather brute force and can definitely be simplified, but it is just algorithmic recursion.

Answer 5

1 + (1 + 2) + (1+ 2+ 3) + ...... + (1 + 2 + 3 + ... n)

Answer 6

You know how many times the second cycle runs, so you can replace the first two cycles with one right? as

 for(ij = 1; ij < (n*(n+1))/2; ij++) for (k = 1; k <= ij; k++) x = x + 1; 

Applying the same formula that you used for the first, where "n" is the time n (n + 1) / 2, you will have ((n (n + 1) / 2) * (n (n + 1)) / 2 + 1)) / 2 - x = x + 1 is satisfied.