Discrete Mathematics for Computer Science

302 CHAPTER 5 Analysis of Algorithms

Each if-then statement makes a single comparison. Three if-then statements are exe-

cuted in a sequence, so three comparisons are made.

Complexity of Sequence

If, for some n E N, an algorithm has blocks B 1 , B 2 ... , B, in sequence and, on input

I to the algorithm, block Bi executes the key operations at most Fi(Bi) times for

1 < i < n, then the entire algorithm executes the key operations at most

FI(BI) + F2 (B2) +.. + Fn (Bn)

times.

If we choose comparison as the key operation in the Ordering Three Values I algorithm

and the blocks are just the three if statements, then

FI(BI) = F 2 (B 2 ) = F 3 (B 3 ) = 1

since the process of Swap will not include any comparisons. The complexity of this algo-

rithm with this key operation is just the constant value 3, and the algorithm is said to be

0(1).

5.3.2 Two Algorithms Illustrating Selection

The next algorithm is like the previous one, except that the writer observed that if one first

tests whether A > B or B > C, then one can use only two tests, not three, for that case.

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

OUTPUT: The list of letters ordered by increasing value

if (A > B or B > C) then /* list is out of order, so */

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

In the Ordering Three Values II algorithm, only two comparisons are made if the list is

in order. On the other hand, if the list is out of order, the algorithm makes two comparisons

to identify that fact plus a sequence of three more comparisons to sort the values, for a

total of five comparisons at worst on any input data. The complexity of this algorithm with

comparison as the key operation is the constant value 5. This algorithm also is a member

of 0(1).