Chapter Review
581
a power of d. The solution of this class of recurrence relations leads to a classification of
divide-and-conquer recurrence relations.
The algorithm for the Tower of Hanoi problem exemplifies first-order recurrence relations. The Fibonacci sequence recurrence relation exemplifies second-order recurrence
relations. The different types of divide-and-conquer recurrence relations are exemplified
by binary search, merge sort, and n-bit multiplication.
9.12.1 Terms, Theorems, Algorithms
9.1-9.3 Summary
TERMS
back substitution
matrix multiplication
boundary value
nonhomogeneous
first order
solution
first-order recurrence relation
Tower of Hanoi
initial value
ALGORITHMS
Iterative Bubble Sort
Selection Sort
Recursive Bubble Sort
Tower of Hanoi
THEOREM
Solution of First-Order Recurrence Relations
9.4 Summary
TERMS
boundary values
particular solution
characteristic equation
second order
Fibonacci sequence
second-order recurrence relation
homogeneous
trivial solution
initial values
THEOREM
Solution of Second-Order Recurrence Relations
9.6-9.10 Summary
TERMS
divide and conquer
multiplication of n-bit numbers
divide-and-conquer relation
ALGORITHM
Binary Search
Merge Sort
THEOREMS
Master Theorem
Solution of Divide-and-Conquer Recurrences