Page 243 - Discrete Mathematics and Its Applications

222 3 / Algorithms

using a summation formula from line 2 in Table 2 in Section 2.4 (and Exercise 37(b) in
Section 2.4). Note that the bubble sort always uses this many comparisons, because it con-
tinues even if the list becomes completely sorted at some intermediate step. Consequently, the
2
bubble sort uses (n − 1)n/2 comparisons, so it has (n ) worst-case complexity in terms of
the number of comparisons used. ▲

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

Solution: The insertion sort (described in Section 3.1) inserts the jth element into the correct
position among the first j − 1 elements that have already been put into the correct order. It does
this by using a linear search technique, successively comparing the jth element with successive
terms until a term that is greater than or equal to it is found or it compares a j with itself and stops
because a j is not less than itself. Consequently, in the worst case, j comparisons are required
to insert the jth element into the correct position. Therefore, the total number of comparisons
used by the insertion sort to sort a list of n elements is
n(n + 1)
2 + 3 + ··· + n = − 1,
2
using the summation formula for the sum of consecutive integers in line 2 of Table 2 of
Section 2.4 (and see Exercise 37(b) of Section 2.4), and noting that the first term, 1, is missing
in this sum. Note that the insertion sort may use considerably fewer comparisons if the smaller
elements started out at the end of the list. We conclude that the insertion sort has worst-case
2
complexity (n ). ▲
In Examples 5 and 6 we showed that both the bubble sort and the insertion sort have
2
worst-case time complexity (n ). However, the most efficient sorting algorithms can sort n
items in O(n log n) time, as we will show in Sections 8.3 and 11.1 using techniques we develop in
those sections. From this point on, we will assume that sorting n items can be done in O(n log n)
time.

Complexity of Matrix Multiplication

The definition of the product of two matrices can be expressed as an algorithm for computing
the product of two matrices. Suppose that C =[c ij ] is the m × n matrix that is the product of the
m × k matrix A =[a ij ] and the k × n matrix B =[b ij ]. The algorithm based on the definition
of the matrix product is expressed in pseudocode in Algorithm 1.

ALGORITHM 1 Matrix Multiplication.

procedure matrix multiplication(A, B: matrices)
for i := 1 to m
for j := 1 to n
c ij := 0
for q := 1 to k
c ij := c ij + a iq b qj
return C {C =[c ij ] is the product of A and B}

We can determine the complexity of this algorithm in terms of the number of additions and
multiplications used.