Page 242 - Discrete Mathematics and Its Applications

3.3 Complexity of Algorithms 221

However, the average-case analysis for the linear search algorithm can be done without difficulty,
as shown in Example 4.

EXAMPLE 4 Describe the average-case performance of the linear search algorithm in terms of the average
number of comparisons used, assuming that the integer x is in the list and it is equally likely
that x is in any position.

Solution: By hypothesis, the integer x is one of the integers a 1 ,a 2 ,...,a n in the list. If x is the
first term a 1 of the list, three comparisons are needed, one i ≤ n to determine whether the end
of the list has been reached, one x = a i to compare x and the first term, and one i ≤ n outside
the loop. If x is the second term a 2 of the list, two more comparisons are needed, so that a total
of five comparisons are used. In general, if x is the ith term of the list a i , two comparisons will
be used at each of the i steps of the loop, and one outside the loop, so that a total of 2i + 1
comparisons are needed. Hence, the average number of comparisons used equals
3 + 5 + 7 + ··· + (2n + 1) 2(1 + 2 + 3 + ··· + n) + n
= .
n n
Using the formula from line 2 of Table 2 in Section 2.4 (and see Exercise 37(b) of Section 2.4),

n(n + 1)
1 + 2 + 3 + ··· + n = .
2
Hence, the average number of comparisons used by the linear search algorithm (when x is
known to be in the list) is

2[n(n + 1)/2]
+ 1 = n + 2,
n
which is (n). ▲

Remark: In the analysis in Example 4 we assumed that x is in the list being searched. It is also
possible to do an average-case analysis of this algorithm when x may not be in the list (see
Exercise 23).

Remark: Although we have counted the comparisons needed to determine whether we have
reached the end of a loop, these comparisons are often not counted. From this point on we will
ignore such comparisons.

WORST-CASE COMPLEXITY OF TWO SORTING ALGORITHMS We analyze the
worst-case complexity of the bubble sort and the insertion sort in Examples 5 and 6.

EXAMPLE 5 What is the worst-case complexity of the bubble sort in terms of the number of comparisons
made?

Solution: The bubble sort described before Example 4 in Section 3.1 sorts a list by performing
a sequence of passes through the list. During each pass the bubble sort successively compares
adjacent elements, interchanging them if necessary. When the ith pass begins, the i − 1 largest
elements are guaranteed to be in the correct positions. During this pass, n − i comparisons are
used. Consequently, the total number of comparisons used by the bubble sort to order a list of
n elements is
(n − 1)n
(n − 1) + (n − 2) + ··· + 2 + 1 =
2