Contents
xvii
8.10 Exercises 539
8.11 Chapter Review 540
8.11.1 Summary 541
8.11.2 Starting to Review 542
8.11.3 Review Questions 543
8.11.4 Using Discrete Mathematics in Computer Science 545
CHAPTER 9
Recurrence Relations
549
9.1 The Tower of Hanoi Problem 549
9.1.1 Recurrence Relation for the Tower of Hanoi Problem 552
9.1.2 Solving the Tower of Hanoi Recurrence 552
9.2 Solving First-Order Recurrence Relations 554
9.2.1 Solving First-Order Recurrences Using Back Substitution 555
9.3 Exercises 558
9.4 Fibonacci Recurrence Relation 561
9.4.1 Second Order-Recurrence Relations 562
9.4.2 Solving the Fibonacci Recurrence 564
9.4.3 Rules for Solving Second-Order Recurrence Relations 566
9.5 Exercises 567
9.6 Divide and Conquer Paradigm 568
9.7 Binary Search 568
9.71 Correctness 569
9.72 Complexity 570
9.8 Merge Sort 571
9.8.1 Correctness 571
9.8.2 Example 572
9.8.3 Complexity 572
9.9 Multiplication of n-Bit Numbers 573
9.10 Divide-and-Conquer Recurrence Relations 576
9.10.1 Complexity of Divide-and-Conquer Recurrence Relations 579