CODEWITHSUNDEEP
c#algorithm
Harris Calvin
Harris Calvin

Reputation: 473

Algorithm time complexity for various nested for loops

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?

Upvotes: 1

Views: 1908

Answers (2)

StriplingWarrior
StriplingWarrior

Reputation: 156459

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.

Upvotes: 3

deathismyfriend
deathismyfriend

Reputation: 2192

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.)

Upvotes: 0

Related Questions