Discrete Mathematics for Computer Science

Complexity of Programs 301

programming has become a powerful new paradigm for program design, it remains neces-

sary to use the fundamental ideas of structured programming in implementing algorithms.

The three control structures used in structured programming are sequence, selection, and

repetition.

Control Structures

Sequence: A list of steps s5 : S2 :... : sk to be performed in the order given.

Selection: A choice of steps. In many programming languages, constructs such as

if-then, if-then-else, select, and case provide the methods to make choices.

Repetition (also called iteration and looping): A block of code is executed repeat-

edly, either for a certain number of times or until some condition becomes true. In

many programming languages, constructs such as for, while, do-while, and repeat-

until provide for repetition. (Repetition can also be accomplished with recursion. The

analysis is often similar, but we will not discuss recursion in this chapter.)

The remaining algorithms of this section, which demonstrate how to determine the

complexity of code using these control structures, will be simple sorting algorithms. The

routine Swap(A, B) will simply interchange the values of these two variables A and B so

that the original value of A ends in B's location and the original value of B ends in A's

location.

INPUT: Distinct alphabetic values for three variables A, B, and C

OUTPUT: The list of alphabetic values ordered by increasing value

if (A > B) then

Swap(A, B)

if (B > C) then

Swap(B, C)

if (A > B) then

Swap(A, B)

print A, B, C

Assume that when the Ordering Three Values I algorithm starts, the three alphabetic
values a, b, and c (ordered as a < b < c) are assigned to the variables A, B, and C in
some order. At the end of the algorithm, the values should satisfy A < B < C. There are
six possible input orders for the three letters a, b, and c. The reader should check that the
algorithm correctly sorts all six possible initial conditions.