Page 391 - Discrete Mathematics and Its Applications

370 5 / Induction and Recursion

by Lemma 1, each of these mergers can be carried out using at most 2 m−k + 2 m−k − 1 =
2 m−k+1 − 1 comparisons. Hence, going from level k to k − 1 can be accomplished using at
most 2 k−1 (2 m−k+1 − 1) comparisons.
Summing all these estimates shows that the number of comparisons required for the merge
sort is at most
m m m
k−1 m−k+1 m k−1 m m
2 (2 − 1) = 2 − 2 = m2 − (2 − 1) = n log n − n + 1,
k = 1 k = 1 k = 1

m
because m = log n and n = 2 . (We evaluated m 2 m by noting that it is the sum of m
k = 1
m
identical terms, each equal to 2 . We evaluated m 2 k−1 using the formula for the sum of
k = 1
the terms of a geometric progression from Theorem 1 of Section 2.4.)
Theorem 1 summarizes what we have discovered about the worst-case complexity of the
merge sort algorithm.

THEOREM 1 The number of comparisons needed to merge sort a list with n elements is O(n log n).

In Chapter 11 we will show that the fastest comparison-based sorting algorithm have
O(n log n) time complexity. (A comparison-based sorting algorithm has the comparison of
two elements as its basic operation.) Theorem 1 tells us that the merge sort achieves this best
possible big-O estimate for the complexity of a sorting algorithm. We describe another efficient
algorithm, the quick sort, in the preamble to Exercise 50.

Exercises

1. Trace Algorithm 1 when it is given n = 5 as input. That 10. Give a recursive algorithm for finding the maximum of
is, show all steps used by Algorithm 1 to find 5!,asis a finite set of integers, making use of the fact that the
done in Example 1 to find 4!. maximum of n integers is the larger of the last integer in
the list and the maximum of the first n − 1 integers in the
2. Trace Algorithm 1 when it is given n = 6 as input. That list.
is, show all steps used by Algorithm 1 to find 6!,asis
done in Example 1 to find 4!. 11. Give a recursive algorithm for finding the minimum of a
finite set of integers, making use of the fact that the min-
3. TraceAlgorithm 3 when it finds gcd(8, 13). That is, show
all the steps used by Algorithm 3 to find gcd(8, 13). imum of n integers is the smaller of the last integer in the
list and the minimum of the first n − 1 integers in the list.
4. Trace Algorithm 3 when it finds gcd(12, 17). That is, n
showallthestepsusedbyAlgorithm3tofindgcd(12, 17). 12. Devise a recursive algorithm for finding x mod m when-
ever n, x, and m are positive integers based on the fact
n
5. Trace Algorithm 4 when it is given m = 5, n = 11, and that x mod m = (x n−1 mod m · x mod m) mod m.
b = 3 as input. That is, show all the steps Algorithm 4
11
uses to find 3 mod 5. 13. Give a recursive algorithm for finding n! mod m when-
ever n and m are positive integers.
6. Trace Algorithm 4 when it is given m = 7, n = 10, and
14. Give a recursive algorithm for finding a mode of a list of
b = 2 as input. That is, show all the steps Algorithm 4
10
uses to find 2 mod 7. integers. (A mode is an element in the list that occurs at
least as often as every other element.)
7. Give a recursive algorithm for computing nx whenever n
15. Devise a recursive algorithm for computing the greatest
is a positive integer and x is an integer, using just addition.
common divisor of two nonnegative integers a and b with
8. Give a recursive algorithm for finding the sum of the a< b using the fact that gcd(a, b) = gcd(a, b − a).
first n positive integers.
16. Prove that the recursive algorithm for finding the sum of
9. Give a recursive algorithm for finding the sum of the the first n positive integers you found in Exercise 8 is
first n odd positive integers. correct.