Java Reference

In-Depth Information

tions still to be performed
. In this case,
n-i
is the exact number of iterations,

but in other loops it may not be. The bound function is useful in determining

worst-case execution time, since it tells us the maximum number of iterations the

loop will make.

Properties of a bound function

In order to be an upper bound on the number of iterations, the bound func-

tion must satisfy two properties:

1. Each iteration must decrease the bound function.

In our example program, execution of the assignment to
i
reduces the value

of expression
n-i
by
1
.

In determining the second property, consider this. It is not enough to see that

the bound function decreases at each iteration. We must also know that at some

point the loop condition becomes false. We do this by requiring that as long as

there is another iteration to perform, the bound function is greater than
0
. We

know there is another iteration to perform if (1) the invariant is true and (2) the

loop condition is true.

Thus, the second property that a bound function must satisfy is this:

2. The invariant, together with loop condition, must imply that the

bound function is greater than
0
.

In our example, from the invariant and the loop condition, we conclude that

i<n
, and from this we conclude
n-i>0
, as required.

7.7

Miscellaneous points about loops

7.7.1

There are no nested loops

We write a program to count the number of primes in
2..99
. Recall that a prime

is an integer that is greater than
1
and is divisible by only
1
and itself.

We can use the natural-number for-loop schema for this purpose and write

the program, with part of it abstract, fairly quickly. The only part that is abstract

and needs to be refined is the question of whether
i
is a prime.

//
Set
x
to the number of primes in
2..99

int
x= 0;

// {
invariant:
x =
the number of primes in
2..i-1 }

for
(
int
i= 2; i != 100; i= i + 1) {

if
(i
is prime
) { x= x + 1; }

Activity

7-6.1

}

Changing the task slightly to fit previously written code

In Sec. 7.4.3, we wrote code to test whether an integer is prime. To prepare

Search WWH ::

Custom Search