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