Counting the Number of Iterations of a Nested Loop

Consider the following nested loop:

for $i$:$=1to4$

for $j$:$=1to3$

$[$Statements in body of inner loop.

None contain branching statements

that lead out of the inner loop.$]$

next $j$

next $i$

How many times will the inner loop be iterated when the algorithm is implemented and run?

Solution The outer loop is iterated four times, and during each iteration of the outer loop, there are three iterations of the inner loop. Hence by the multiplication rule, the total number of iterations of the inner loop is $4*3=12.$ This is illustrated by the trace table below.

$\backslash$table$[[i,1,,,2,,,3,,,4,,],[j,1,2,3,1,2,3,1,2,3,1,2,3],[ubrace(3$ubrace$),$ubrace$(3$ubrace$),,,,,,,,,,,]]$

$12$

Exercise

$1.$

for $j$:$=1tom$

for $k$:$=1ton$

$[$Statements in body of inner loop.

None contain branching statements that lead outside the loop.$]$

next $k$

next $j$

$3.$ for $i$:$=5$ to $50$

for $j$:$=10$ to $20$

$[$Statements in body of inner loop.

None contain branching statements that lead outside the loop.$]$

next $j$

next $i$

$2.$

for $i$:$=1$ to $m$

for $j$:$=1$ to $n$

for $k$:$=1$ to $p$

$[$Statements in body of inner loop.

None contain branching statements

that lead outside the loop.I

next $k$

next $j$

next $i$