s
Section 5.6 The Mighty Mod Function
423
20. An algorithm to determine whether a propositional wff with n statement letters is a tautology works by
assigning, one at a time, all possible sets of truth values to the statement letters. The unit of work for this
algorithm is the examination of one set of truth values. Explain why this algorithm is Θ(2
n
) in the worst
case.
For Exercises 21–26, use the master theorem to determine an order-of-magnitude expression for the work done.
21. S(n) = 2S a
n
4
b + n
2
22. S(n) = 4S a
n
3
b + n
23. S(n) = 4S a
n
4
b + n
24. S(n) = 4S a
n
2
b + n
2
25. S(n) = 3S a
n
3
b + "n
26. S(n) = 2S a
n
2
b + n
3
27. The worst-case recurrence relation for comparisons done by the MergeSort sorting algorithm is
C(1) = 0
C(n) = 2Ca
n
2
b + (n − 1) for n ≥ 2, n = 2
m
a. Use the master theorem to find an order-of-magnitude expression for the solution to the related recurrence relation.
C′(n) = 2C′a
n
2
b + n for n ≥ 2, n = 2
m
b. Compare the result of part (a) with the exact solution to C(n) (Exercise 22 of Section 3.3).
28. Prove the master theorem for the case where a = b
c
. (Hint: Start with Equation (5). Also remember that a
change of base of logarithms only involves multiplication by a constant.)
S e c t I o n 5 . 6 the Might y Mod FunCtion
In Section 5.4 we defined the modulo n function as follows:
If x = qn + r, 0 ≤ r < n, then x mod n = r.
In other words, x mod n is the nonnegative remainder (also called the residue of x
modulo n) when x is divided by the positive integer n. This seemingly innocuous
function turns up in a surprising number of applications, some of which will be
explored in this section.