Incremental Java
Counting Iterations

Counting Iterations

It's a useful skill to look at a loop and determine how many iterations it makes.

Example 1

How many iterations?
int count = 1 ;
while ( count <= num )
{
   count++ ;
}
Answer: num iterations. We did this in the first while loop example. Notice that num controls the number of iterations, not the looping variable.

Example 2

How many iterations?
int count = 0 ;
while ( count < num )
{
   count++ ;
}
Answer: num iterations.

Example 3

How many iterations?
int count = 0 ;
while ( count <= num )
{
   count++ ;
}
Answer: num + 1 iterations. Check the condition of the loop.

Example 4

How many iterations?
int count = low ;
while ( count < high )
{
   count++ ;
}
Answer: high - low iterations (assuming low <= high).

How can you convince yourself of this? You know this has to work if low = 0. So how many iterations if low is 0. It's high iterations. That's also high - low iterations.

This is a little complicated, but you can see it by trying to make this loop look like Example 1.

Example 5

How many iterations?
int count = low ;
while ( count <= high )
{
   count++ ;
}
Answer: (high - low) + 1 iterations (assuming low <= high).

The change from < to <= adds 1 to the number of iterations.

Skipping by 2

What happens if we change count++ to count += 2 or even count += jump (where jump >= 2)?
int count = 0 ;
while ( count <= num )
{
   count += 2 ;
}
Since we're jumping by two's, we expect the number of iterations to divide by 2. If you count from 1 to 100, skipping by 2's, you expect to say about 50 numbers.

Suppose we start at 0 and end at num - 1. The number of iterations may depend on whether num is even or odd. Let's figure out the formula for a small number.

Suppose num is 8. Then, if we start at 0, we should go 0, 2, 4, and 6, which is 4 iterations (8 is too big, since we only iterate up to 8 - 1 = 7).

Suppose num is 9. Then, if we start at 0, we should go 0, 2, 4, 6, and 8 which is 5 iterations.

The answer appears to be (num + 1) / 2 iterations (using integer division where we truncate any fractions). num / 2 doesn't work because 9 / 2 is 4 (if you truncate the result). Of course, we could use a formula that rounds up, but it's more common in Java to use truncation.

Try to find a formula for the number of iterations if you skip by 3's. When you skip by 2's, you have two cases: the number is even, the number is odd. When you skip by 3's, you have 3 cases.

Try to find a formula for the number of iterations in
int count = low ;
while ( count <= high )
{
   count += jump ;
}

Looping Variable Doesn't Control Number of Iterations

In all of the formulas that count the number of iterations, none of them use the looping variable. Instead, it uses the variable (or expression) that the looping variable is compared against.

Thus, num, low, and high determine the number of iterations.