Discrete Mathematics for Computer Science

306 CHAPTER 5 Analysis of Algorithms

before each time the loop is executed and once again at the end. The result of that final test

shows that it is not necessary to execute the loop another time.

Complexity of Repetition

If an algorithm contains a loop B, where:

* On input I, the loop is executed at most n times for some n e N, and

* On input I, for 1 < i < n, the ith execution of the body of the loop executes the

key operations at most Fi (Bi) times, and

* The test of whether to stop or to execute the loop another time executes the key

operations at most c times,

then the number of times the entire algorithm executes the key operations during the

loop is at most

n

E(c + Fi(Bi)) + c

i=1

Normally, when the loop controls the number of times the body of the loop is exe-

cuted, the value of c is zero, because incrementing and testing a counter is usually not a

key operation. We can now compute the complexity of the BubbleSort I algorithm, with

comparison of the elements of the list as the key operation. Note that the termination con-

dition here does not involve a key operation-it compares indices, not array elements-so

C =0.

Analysis of the Inner Loop. The block Bi consists of lines 3 and 4. Hence, the number

of comparisons is always 1; that is, Fi(Bi) = 1 for i = 1. N - 1. So, by the previous

formula, the total number of comparisons is

N-1

#comparisons < Y I = N- 1

Position= 1

Analysis of the Outer Loop. Here each block Bi of the outer loop is just the (whole)

inner loop. So, Fi (Bi) = N - 1. The outer loop is executed N - 1 times. Hence, the total

number of comparisons is

N-1

# comparisons < Y (N-) = (N- 1)2

Pass=1

Thus, the number of comparisons made by the BubbleSort I algorithm on an input list

of size N is

O((N - 1)2) = O(N^2 - 2N + 1) = O(N^2 )

by Theorem 6 of Section 5.1.3.