Loops - Multimedia Introduction to Programming Using Java - page 255

that k ≤ n . For example, if s initially contains 2 values, then initially k+1=n ,
and incrementing k and decrementing n makes k>n .

7.6.3 Off-by-one errors

An off-by-one error occurs when a loop iterates once too many or once too few
times. Many people will tell you that off-by-one errors arise from carelessness,
but that is all they say. They do not tell you how to develop the loop condition so
that off-by-one errors do not occur.
If you follow the guidelines given in this text, you will rarely make off-by-
one errors. As we have said earlier, to find a suitable condition for the loop, com-
pare the invariant, for example:

Activity
7-5.4

invariant: The i smallest circles have been drawn
with the postcondition, for example:

postcondition: The n smallest circles have been drawn
and determine a relation that, together with the invariant, implies the postcondi-
tion, for example”

relation: i=n
The complement of this relation is then the loop condition:

loop condition: i!=n
Follow this little methodology and you will rarely make off-by-one errors.

7.6.4 The bound function of a loop

We have been rather informal about checking that a loop makes progress toward
termination. We now look in more detail at what it takes to determine this. We
illustrate the technique using this loop:

Activity
7-5.1

// Draw n circles with centers (x , y) and radii of 4 , 8 , 12 , …
int i= 0;
// { invariant: i smallest circles were drawn and 0≤i<n }
while (i != n) {
int r= 5+5*i; // radius of circle i
g.drawOval(x - i , y-i , 2*i , 2 * i);
i= i + 1;

}
We introduce what we call a bound function , in this case:

Bound function: n-i
This is an integer expression that gives an upper bound on the number of itera-