Analyzing loops

Section 5.5 Analyzing loops

While conceptually simple, loops actually turn out to be a bit tricky to get right. Unfortunately stepping through the execution of a loop line by line can be tedious due to the repetition—imagine if you had a loop that ran a million times; you wouldn’t want to step through that! So it’s useful to have a few techniques for analyzing loops a bit more abstractly.

🔗

Often the main question we have about a loop is simply how many times will the body run? Sometimes this is in order to do run-time analysis in order to get an estimate of how long a program will take. (A loop that runs a billion times is going to take a lot longer than one that runs ten times even though, textually, the code of the two loops might be identical.) More often we know how many times the loop is supposed to run and we want to make sure we’ve written the loop correctly.

🔗

In particular, a common bug that occurs in loops is called a fencepost error or an off-by-one error which is when a loop iterates one fewer times (or occasionally one more) than it should. The name comes from the mistake that many people make when asked how many fenceposts—the uprights in a fence—you need to build a hundred foot fence with fenceposts every ten feet. If you think the answer is ten you have a fencepost error because the correct answer is eleven.

🔗

If all else fails, sometimes it is necessary to trace through some or all the iterations of loop. If so we’ll want to use a techniue called a trace table to keep track of things.

🔗

In this lesson, we’ll look at all three of these ways of analyzing loops.

🔗

Subsection 5.5.1 Counting loop iterations

The simplest way to know how many times the body of a loop is going to run is to write the loop simply. Here’s is the canonical for loop:

🔗

for (int i = 0; i < n; i++) {
  // whatever
}

Whenever you can, we should write our loops in this form. There are a few features that make it the canonical loop:

🔗

The loop variable, i starts at 0.

🔗
The loop variable is incremented by one in the updater.

🔗
The comparison uses < so the maximum value of i is one less than n.

🔗

🔗

After ensuring those features are present, any Java programmer should be able to look at this loop and almost instantly respond to the question, “How many times will the body run?” with the answer, “n times.” In this case n is a variable but it could be any expression.

🔗

If it was a literal number like 10 the answer would be “ten times”. And if it was some other expression like s.length() where s was a String, the answer would be “once for every character in s”.

🔗

Note that it is possible for code in the loop body to cause the loop to complete early. For instance, a return statement causes an immediate return from the method, breaking out of the loop early. But for purposes of analyzing loops, we typically assume nothing like that happens in the body.

🔗

Activity 5.5.1. A canonical loop.

How many times does this loop run? (Assume the body doesn’t contain any code to cause the loop to complete early.)

🔗

for (int i = 0; i < 100; i++) {
  // whatever
}

100
🔗
Yes.
101
🔗
That would be correct if the condition used <= rather than <.
99
🔗
You may have a fencepost error. While the largest value i will take on in the body of the loop is 99, there are one hundred numbers between 0-99, inclusive.
It’s an infinite loop
🔗
Not sure why you’d think that. Check again.

🔗

Often the easiest way to analyze a non-canonical loop is to turn into into a canonical loop by accounting for whatever things make it non-canonical.

🔗

For instance if a loop uses <= rather than < we can change the <= to a < if we add one to the limit. And assuming we’re only trying to figure out how many times the loop body will run we’re can add or subtract the same amount from both the initial value and the limit to get a canonical loop that will run the same number of times (though obviously with different values for the loop variable).

🔗

Table 5.5.1. Non-canonical and canonical loops with same number of iterations

🔗

Non-canonical loop	Canonical loop
`for (int i = 0; i <= 9; i++)`	`for (int i = 0; i < 10; i++)`
`for (int i = 1; i < 11; i++)`	`for (int i = 0; i < 10; i++)`
`for (int i = 10; i < 20; i++)`	`for (int i = 0; i < 10; i++)`

We can also use this trick to analyze loops that run backwards. To convert a backwards loop to a canonical forwards loop we first convert it to an equivalent (except for the order, obviously) forward loop and put that forward loop into canonical form.

🔗

To turn around a backwards loop, write a forwards loop where the initial value of the loop variable is value of the limit in the originial loop if it is written with >= and one greater than the limit if it is written with >. And the limit in the forwards loop is one greater than the initial value in the backwards loop.

🔗

Table 5.5.2. Backwards loops to canonical loops with same number of iterations

🔗

Backwards loop	Forwards loop	Canonical loop
`for (int i = 9; i >= 0; i--)`	`for (int i = 0; i < 10; i++)`	`for (int i = 0; i < 10; i++)`
`for (int i = 10; i > 0; i--)`	`for (int i = 1; i < 11; i++)`	`for (int i = 0; i < 10; i++)`
`for (int i = 19; i >= 10 i--)`	`for (int i = 10; i < 20; i++)`	`for (int i = 0; i < 10; i++)`

Activity 5.5.2. A backwards loop.

How many times does this loop run? (Assume the body doesn’t contain any code to cause the loop to complete early.)

🔗

for (int i = 20; i > 10; i--) {
  // whatever
}

10
🔗
Yes.
11
🔗
That would be correct if the condition used >= rather than <.
9
🔗
You may have a fencepost error. While the largest value i will take on in the body of the loop is 20 and the smallest is 11, there are ten numbers between 11-20, counting 11 and 20 themselves.
It’s an infinite loop
🔗
Not sure why you’d think that. Check again.

🔗

Activity 5.5.3. Line of stars.

How many stars are printed out in this loop? Depends how many iterations the loop runs. See if you can convert the loop to a canonical loop in your head or on a piece of paper to predecict how many iterations it will run before you run the code.

🔗

Translating between non-canonical and canonical loops is a good skill to have. In general we should write loops in canonical form whenever we can so that people reading our code (including ourselves!) can see at a glance what is going on. That will also make the times when we have to write a non-canonical loop because something tricky is going on stand out so we know to pay extra careful attention to that code.

🔗

But we can further distill the process of converting to a canonical loop if all we care about is how many times the loop body will run. For any loop all we really need to know is the smallest value the loop variable will take on and the limit, which is one greater than the largest value. I.e. these are the initial value and the value to the right of the < in the condition of a canonical loop. Then the number of times the loop will run is just \(limit - smallestValue\text{.}\)

🔗

Table 5.5.3. Using \(limit - smallestValue\) formula

🔗

Loop	Smallest	Limit	Iterations
`for (int i = 0; i < 10; i++)`	0	10	10
`for (int i = 0; i <= 9; i++)`	0	10	10
`for (int i = 1; i < 11; i++)`	1	11	10
`for (int i = 10; i < 20; i++)`	10	20	10
`for (int i = 9; i >= 0; i--)`	0	10	10
`for (int i = 10; i > 0; i--)`	1	11	10
`for (int i = 19; i >= 10 i--)`	10	20	10

🔗

Subsection 5.5.2 Analyzing nested loops

Recall that nested loops are just loops within the body of another loop. Since the whole inner loop runs all of its iterations every time the outer loop’s body runs once, the total number of times the body of a nested loop runs is the number of times the outer loop runs multiplied by the number of times the inner loop runs. Here is an example of a nested loop that prints a rectangle of stars:

🔗

Activity 5.5.4. Grid of stars.

How many stars are printed out by the following loops? How many times do the loops run? Figure it out in our head or on paper before you run the code.

🔗

Analyzing the nested loops using the formula from above, we see that the outer loop has a smallest value of 0 and a limit of 5 so it runs \(5 - 0 = 5\) times. And the inner loop has a smallest value of 0 and a limit of 10 so it runs \(10 - 0 = 10\) times. And five times ten gives us fifty total stars.

🔗

Activity 5.5.5. Swap rows and columns.

The code in the previous problem printed a grid of five rows and ten columns. Which of the following print a grid of ten rows and five columns?

🔗

for (int row = 0; row < 10; row++) {
    for (int col = 0; col < 5; col++) {
        System.out.print("*");
    }
    System.out.println();
}

Yes.

for (int row = 0; row <= 5; row++) {
    for (int col = 0; col <= 10; col++) {
        System.out.print("*");
    }
    System.out.println();
}

Yes.

for (int row = 0; row < 5; row++) {
    for (int col = 0; col < 10; col++) {
        System.out.print("*");
        System.out.println();
    }
}

Yes.

🔗

Subsection 5.5.3 Trace tables

Because they are hard enough to get right even when they’re simple, it’s a good idea to keep loops as simple as possible. But sometimes we come across loop that contain multiple variables that all change in the body of the loop and which may all be involved in the loop’s condition which makes all our simpler loop analysis techniques less useful. In those situations it may be time to pull out a piece of scratch paper and create a trace table.

🔗

A trace table is a table that we use to track the values of the variables in a loop at each iteration of the loop. Each row of the table represents one iteration of the loop and each column holds the value for one variable. To see how to build a trace table we’ll use this example loop.

🔗

int var1 = 3;
int var2 = 2;

while ((var2 != 0) && ((var1 / var2) >= 0)) {
    var1 = var1 + 1;
    var2 = var2 - 1;
}

This is not absurdly complicated but it’s definitely not a simple counting loop.

🔗

To make a trace table, the first step is to count the variables that are assigned values in the body of the loop Make a table with as many columns as variables plus one. Label the first column “iteration”. Then label the remaining columns with variable names in the order that they are assigned new values in the loop body. The header row for a trace table for this loop would look like this:

🔗

Iteration	`var1`	`var2`

Now to fill out the table add row for iteration 0, i.e. before the loop body has run and fill in the initial value of each variable in the appropriate column.

🔗

Iteration	`var1`	`var2`
0	3	2

Then add rows to the table, Before you add a new row, check whether the loop condition given the values of the variables recorded in the current row. If it is false the loop ends and the table is complete. But if it’s true, add a row, increasing the number in the iteration column, and then mentally executing the code in the loop to determine the new value of each variable.

🔗

If one variable depends on a variable to its left in the table, use the value in the current row; otherwise—including if the variable depends on itself—use the value from the previous row. (This is why it’s important to put the variables into columns in the right order.)

🔗

The completed table for the loop above should look like this

🔗

Iteration	`var1`	`var2`
0	3	2
1	4	1
2	5	0

From the last row of a completed trace table we can read off how many times the body was executed from the iteration column and the final values of all the variables. Note it even works if if the loop’s condition is never true and the body never executes. In that case the last row will be for iteration 0 and the final values of all the variables will be whatever they were initialized to.

🔗

Activity 5.5.6. Check the trace table.

Make sure you understand how the table was filled out. You may want to get a piece of paper and try to make your own table and see if you get the same answer as above. Or you can click the Code Lens button to trace the code below or add print statements like System.out.println("var1: " + var1 + " var2: " + var2); before, inside, and after the loop and Run the code to see how the variables change.

🔗

Activity 5.5.7.

What are the values of var1 and var2 when the code finishes executing?

🔗

int var1 = 0;
int var2 = 2;

while ((var2 != 0) && ((var1 / var2) >= 0))
{
   var1 = var1 + 1;
   var2 = var2 -1;
}

var1 = 1, var2 = 1
🔗
The loop stops one of two ways, when var2 = 0 or when var1 / var2 = 0 - neither is true in this case
var1 = 2, var2 = 0
🔗
The loop stopped because var2 = 0. After the first execution of the loop var1 = 1 and var2 = 1. After the second execution of the loop var1 = 2 and var2 = 0. This stops the loop and doesn’t execute the second part of the complex conditional.
var1 = 3, var2 = -1
🔗
The loop stops one of two ways, when var2 = 0 or when var1 / var2 = 0 - neither is true in this case
var1 = 0, var2 = 2
🔗
The loop stops one of two ways, when var2 = 0 or when var1 / var2 = 0 - neither is true in this case
The loop will cause a run-time error with a division by zero
🔗
Even though var1 = 2 and var2 = 0 when the conditional is executed the first condition is true so the rest of the complex conditional won’t execute.

🔗

Activity 5.5.8.

What are the values of x and y when the code finishes executing?

🔗

int x = 2;
int y = 5;

while (y > 2 && x < y)
{
   x = x + 1;
   y = y - 1;
}

x = 5, y = 2
🔗
This would be true if the and (&&) was an or (||) instead. But in a complex conditional joined with and (&&) both conditions must be true for the condition to be true.
x = 2, y = 5
🔗
This would be true if the loop never executed, but both conditions are true so the loop will execute.
x = 5, y = 2
🔗
This would be true if the values were swapped, but they are not.
x = 3, y = 4
🔗
This would be true the loop only executed one time, but it will execute twice.
x = 4, y = 3
🔗
The first time the loop changes to x = 3, y = 4, the second time x = 4, y = 3 then the loop will stop since x is not less than y anymore.

🔗

Activity 5.5.9. Tracing a hairy loop.

Here is a particularly hairy loop. Get a piece of scratch paper and make a trace table. When you are done, click “Answer” and compare to see if you got it right.

🔗

int x = 0;
  int y = 4;
  int z = 2;

  while (x < 3 && y >= 0) {
    x = y - z;
    y--;
    z *= 2;
  }
}

Answer.

Iteration	`x`	`y`	`z`
0	0	4	2
1	2	3	4
2	-1	2	8
3	-6	1	16
4	-15	0	32
5	-32	-1	64

🔗

Subsection 5.5.4 Limits of trace tables

It’s useful to know how to build trace tables and actually making them is good practice for following a mechanical procedure precisely which is good practice for thinking about how code works.

🔗

In actual programming practice, trace tables are of limited use. They have the virtue that, similar to boolean truth tables, once you master the mechanics you can reliably crank them out without having to think too hard. On the other hand, code tracing is only possible if we know the initial values. And if we knew the initial values we could just run the program to find out what it does. Or write a program to print out the trace table! To actually understand a loop via tracing you might need to trace it multiple times with different initial values. Which is even more tedious than making just one.

🔗

However there are times (particularly on the AP exam) when a trace table can quickly and reliably answer certain questions about a piece of code. If you ever find yourself confronting as hairy a loop as the one in Activity 5.5.9 Tracing a hairy loop, you way want to make a trace table to help yourself understand what’s going on so you can rewrite it to be simpler. Unless the loop is on the AP exam in which case just shake your fist at the AP exam writers and then answer the question.

🔗

Subsection 5.5.5 Coding Challenge: POGIL Analyzing Loops

We encourage you to do this activity as a POGIL (Process Oriented Guided Inquiry Learning) group activity. POGIL groups are self-managed teams of up to 4 students where everyone has a POGIL role and works together to solve the problems, making sure that everyone in the team participates and learns.

🔗

Do the following exercises in your group. Make sure you draw the trace tables keeping track of all the variables in the loops. Use the formulas to determine how many times the loops run. If your group finishes early, do some of the multiple-choice problems in the Practice and Summary section of this unit.

🔗

Activity 5.5.10.

How many times does the following code print a *?

🔗

for (int i = 3; i < 8; i++)
{
    for (int y = 1; y < 5; y++)
    {
        System.out.print("*");
    }
    System.out.println();
}

40
🔗
This would be true if the outer loop executed 8 times and the inner 5 times, but what is the initial value of i?
20
🔗
The outer loop executes 7-3+1=5 times and the inner 4-1+1=4 so this will print 5 * 4 = 20 stars.
24
🔗
This would be true if the outer loop executed 6 times such as if it was i <= 8.
30
🔗
This would be true if the inner loop executed 5 times such as if it was y <= 5.

🔗

Activity 5.5.11.

What does the following code print?

🔗

for (int i = 2; i < 8; i++)
{
    for (int y = 1; y <= 5; y++)
    {
        System.out.print("*");
    }
    System.out.println();
}

A rectangle of 8 rows with 5 stars per row.
🔗
This would be true if i was initialized to 0.
A rectangle of 8 rows with 4 stars per row.
🔗
This would be true if i was initialized to 0 and the inner loop continued while y < 5.
A rectangle of 6 rows with 5 stars per row.
🔗
The outer loop executes 8-2+1=6 times so there are 6 rows and the inner loop executes 5-1+1=5 times so there are 5 columns.
A rectangle of 6 rows with 4 stars per row.
🔗
This would be true if the inner loop continued while y < 5.

🔗

Activity 5.5.12.

What does the following print?

🔗

for (int i = 3; i <= 9; i++)
{
   for (int j = 6; j > 0; j--)
   {
       System.out.print("*");
   }
   System.out.println();
}

A rectangle of 9 rows and 5 stars per row.
🔗
Did you notice what i was initialized to?
A rectangle of 6 rows and 6 stars per row.
🔗
It would print 6 rows if it was i < 9.
A rectangle of 7 rows and 5 stars per row.
🔗
It would print 5 stars per row if it was j > 1.
A rectangle of 7 rows and 6 stars per row.
🔗
The outer loop executes 9 - 3 + 1 = 7 times and the inner 6 - 1 + 1 = 6 times.

🔗

Activity 5.5.13.

Consider the following code segment. How many times is the string “Hi!” printed as a result of executing the code segment?

🔗

int i = 0;
while (i <= 4)
{
  for (int j = 0; j < 3; j++)
  {
    System.out.println("Hi!");
  }
  i++;
}

15
🔗
The outer loop executes 4-0+1=5 times and the inner loop 2-0+1=3, so hi is printed 5*3 = 15 times
12
🔗
The outer loop runs 5 times for i = 0, 1, 2, 3, 4.
10
🔗
The inner loop runs 3 times for j = 0, 1, 2.
8
🔗
The outer loop runs 5 times for i = 0, 1, 2, 3, 4.

🔗

Subsection 5.5.6 Summary

(AP 2.12.A.1) A statement execution count indicates the number of times a statement is executed by the program. Statement execution counts are often calculated informally through tracing and analysis of the iterative statements.
🔗

🔗
A trace table can be used to keep track of the variables and their values throughout each iteration of the loop.
🔗

🔗
The number of times a loop executes can be calculated by largestValue - smallestValue + 1 where these are the largest and smallest values of the loop counter variable possible in the body of the loop.
🔗

🔗
The number of times a nested for-loop runs is the number of times the outer loop runs times the number of times the inner loop runs.
🔗

🔗
In non-rectangular loops, the number of times the inner loop runs can be calculated with the sum of natural numbers formula n(n+1)/2 where n is the number of times the outer loop runs or the maximum number of times the inner loop runs.
🔗

🔗

🔗

You have attempted of activities on this page.

🔗

Prev Top Next