Design and Analysis of Algorithms

Proof Rules—Basics 137

6.5 CORRECT TERMINATION OF ALGORITHMS

Till now we have discussed that the correct results are produced by algorithm which are only a part of the

process involved in proving the program correctness. The other part is to prove that the algorithms terminate

in fi nite number of steps. As far as termination is concerned, loops are almost always suspect and they should

be properly checked.

Let us consider the

WHILE-DO loop again, from a slightly different perspective, see Fig. 6.14.

B

P

False

A

S

P

here B may or may not be True

True

D

C

0 £ e < e0

0 < e = e0

S

P Ù B

0 £ e < v

0 < e = v

Effect of s on

e is such that

P Ù ØB

Fig. 6.14 Derivation of ...