1

I have a question regarding this SO post: Understanding How Many Times Nested Loops Will Run

In there the general formula for 3 nested for loops is: n(n+1)(n+2)/3. I don't really know why the 2nd inner loop runs n+1 times while the outer loop runs n times (wouldn't the inner loop run once more before it exits out of the for loop? Either way...the general formula is

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

Here, r is the number of nested loops.

I am wondering if this formula is always the same for nested loops or if it changes based on what the comparison is inside the for loops...If it is based on comparison then how can I determine the formula if on an exam I am given some different for loops? How can I generate or come up with this formula if the comparison for the for loops is not the same as the comparison in the SO post which creates that formula?

Improve this question
4
  • It's just the sum of arithmetic progression. You can compute the total number of iterations using whatever method you want. Commented Nov 5, 2013 at 5:56
  • @Mikhail I don't really understand how I can derive a formula. Commented Nov 5, 2013 at 5:58
  • 2
    There is no general formula for complexity of unknown piece of code. "3 nested loops" does not define algorithm well enough to make any estimates. Commented Nov 5, 2013 at 5:58
  • @AlexeiLevenkov In the case where the inner loop's local counter variable is a function of the outer loop's local counter variable, how can I derive the formula? So say one for loop is (i=0; i<array.Length; i++) and another for loop inside is for (k=i-1; k<array.Length-2; k++). How would I found out how many times code inside the 2nd for loop runs? Commented Nov 5, 2013 at 6:05

2 Answers 2

Reset to default
3

You'll have to train your mind to recognize and follow the patterns in execution, and come up with a formula for specific situations. The general rule of thumb is that if one for loop will run the code inside of it x times, and it has a loop inside of it that will run y times, then the code inside the inner loop will run x*y times.

The most common type of for loop starts at zero and increments by 1 until it reaches a certain number, like so:

for(int i = 0; i < x; i++)
    for(int j = 0; j < y; j++)
        for(int k = 0; k < z; k++)
            // code here runs x * y * z times

To answer your question, if you change any part of any of the for loops, it will change the number of times the inner code is executed. You need to identify how many times that will be by thinking about the logical code execution.

for(int i = 1; i < x; i++)
    for(int j = 0; j < y * 2; j++)
        for(int k = 0; k < z; k += 2)
            // code here runs (x - 1) * (y * 2) * (z / 2) times

In the above example, each for loop is tweaked in a different way. Notice how the overall formula for the number of times run stays pretty much the same, but now each loop is running a different number of times each time it gets hit.

Things become more complicated when the loops' variables affect more than one loop.

for(int i = 0; i < x; i++)
    for(int j = i; j < y; j++) // notice how `j` starts as `i`
        // Code here runs `y` times the first time through the outer loop,
        // then `y - 1` times,
        // then `y - 2` times,
        // ...
        // if x < y, the pattern continues until the xth time,
        // when this loop runs `y - x` times.
        // if x > y, the pattern will stop when y == x, and
        // code here will run 0 times for the remainder of
        // the loops.

So in this last example, assuming x < y, the loop will run y + (y-1) + (y-2) ... + (y-x) times.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

+1 for excellent explanation. Maybe you should have mentioned it is even more complicated if the loop variables are problem dependent (e. g. sorting algorithms). In that case you can compute best, worst, and average complexity.
0

It changes based on the inner values. Example. 

        for (int i = 0; i < 100; i++)
        {
            //this loop will run 100 times.
            for (int i1 = 0; i1 < 100; i++)
            {
                // This will run 100 times every outer loop int.
                // This means that for each index i in the outer loop this will run 100 times. 
                // The outer loop runs 100 time and this runs 10,000 times in total.
            }
        }



        for (int i = 0; i < 100; i++)
        {
            //this loop will run 100 times.
            for (int i1 = 0; i1 < 10; i++)
            {
                // This will run 10 times every outer loop int.
                // This means that for each index i in the outer loop this will run 10 times. 
                // The outer loop runs 100 time and this runs 1,000 times in total.
            }
        }

An easier way to look at it may be this. 

        for (int i = 0; i < 10; i++)
        {
            //this loop will run 10 times.
            Console.WriteLine("int i = " + i.ToString()");
            for (int i1 = 0; i1 < 10; i++)
            {
                // This will run 10 times every outer loop int.
                // This means that for each index i in the outer loop this will run 10 times. 
                // The outer loop runs 10 time and this runs 100 times.
                Console.WriteLine("int i2 = " + i2.ToString()");
            }
        }

That will output this.

        int i = 0
        int i2 = 0
        int i2 = 1
        int i2 = 2
        int i2 = 3
        int i2 = 4
        int i2 = 5
        int i2 = 6
        int i2 = 7
        int i2 = 8
        int i2 = 9
        int i = 1
        int i2 = 0
        int i2 = 1
        int i2 = 2
        int i2 = 3
        int i2 = 4
        int i2 = 5
        int i2 = 6
        int i2 = 7
        int i2 = 8
        int i2 = 9

and so on.

The formula is based on the inner loop numbers. (On when the loop ends.)

Improve this answer

2 Comments

my prof assigns the inner loop's local variable as a function of the outter for loop's local variable. So instead of saying i1=0 he could say i1=i. So now you can imagine it is slightly harder to tell how often the inner loop runs because it is a function of the outer loop. How would I do it in that case? Do I just brute force by writing down what the counters will be like when the code runs or could I use some formula.
You can use an integer counter and increase an integer every loop. A formula is better though as it is less data to process. Basically you can take the numbers and multiply them all out if the start int is the same. example if you change i1 < 20 in the first one you take i * 20 and that will give you 2,000 instead of the 10,000 times it ran.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.