CODEWITHSUNDEEP
algorithmloopsfor-loopprinting
Dr.Doofus
Dr.Doofus

Reputation: 55

Nested loop execution

This is a really simple question, but for some reason I'm getting confused and it's annoying. 

def test():
for i from Lo1 to Hi1:
    for j from Lo2 to Hi2:
    body()

How many times will body() execute for: Lo1=1, Hi1=n, Lo2=i-2, Hi2=i+2

The answer is 5n times, but I have no idea how they get it!

Upvotes: 2

Views: 143

Answers (3)

aakansha
aakansha

Reputation: 695

Suppose there is a for loop with Java code 

for(int i=3;i<=6;i++)
{
    //Statements to be executed
}

The loop will execute 4 times (i=3,4,5,6)

How to calculate?

formula=upper bound-lower bound+1

so in the above loop it will be 6-3+1=4(upper bound=6,lower bound=3)

In your question upper bound=i+2

lower bound=i-2

total number of times inner loop execute=i+2-(i-2)+1=i+2-i+2+1=5

the outer loop will execute n times so just multiply with n

hence answer becomes 5*n=5n

Upvotes: 1

Khurram Sharif
Khurram Sharif

Reputation: 504

Lo2=i-2, Hi2=i+2 Inner Loop

So (i-2)to(i+2)=5 Alternations EG: i-2 , i-1 , i , i+1 , i+2

Like (-2) to (+2)=-2,-1,0,1,2

Lo1=1, Hi1=n Outer Loop

1 to N

So Total Inner* Outer

5*N=5N

Upvotes: 3

Grisha Weintraub
Grisha Weintraub

Reputation: 7986

I think the easiest way to understand is to run it.

For example for n=10, the following java code prints values of i and j in each iteration :

 for (int i=0; i<=10; i++){
     for (int j=i-2; j<=i+2; j++)
         System.out.println("i = " + i + ", j= " + j);
 }

The result is as follows:

i = 0, j= -2
i = 0, j= -1
i = 0, j= 0
i = 0, j= 1
i = 0, j= 2
i = 1, j= -1
i = 1, j= 0
i = 1, j= 1
i = 1, j= 2
i = 1, j= 3
i = 2, j= 0
i = 2, j= 1
i = 2, j= 2
i = 2, j= 3
i = 2, j= 4
i = 3, j= 1
i = 3, j= 2
i = 3, j= 3
i = 3, j= 4
i = 3, j= 5
i = 4, j= 2
i = 4, j= 3
i = 4, j= 4
i = 4, j= 5
i = 4, j= 6
i = 5, j= 3
i = 5, j= 4
i = 5, j= 5
i = 5, j= 6
i = 5, j= 7
i = 6, j= 4
i = 6, j= 5
i = 6, j= 6
i = 6, j= 7
i = 6, j= 8
i = 7, j= 5
i = 7, j= 6
i = 7, j= 7
i = 7, j= 8
i = 7, j= 9
i = 8, j= 6
i = 8, j= 7
i = 8, j= 8
i = 8, j= 9
i = 8, j= 10
i = 9, j= 7
i = 9, j= 8
i = 9, j= 9
i = 9, j= 10
i = 9, j= 11
i = 10, j= 8
i = 10, j= 9
i = 10, j= 10
i = 10, j= 11
i = 10, j= 12

You can see now that there are 10 iterations for i, and for each i you have 5 iterations of j(from i-2 to i+2). Hence 50 (5*N) iterations in total.

Upvotes: 1

Related Questions