xii
Contents
4.10 Chapter Review 275
4.10.1 Summary 275
4.10.2 Starting to Review 277
4.10.3 Review Questions 279
4.10.4 Using Discrete Mathematics in Computer Science 280
CHAPTER 5
Analysis of Algorithms
283
5.1 Comparing Growth Rates of Functions 284
5.1.1 A Measure for Comparing Growth Rates 284
5.1.2 Properties of Asymptotic Domination 289
5.1.3 Polynomial Functions 291
5.1.4 Exponential and Logarithmic Functions 293
5.2 Exercises 296
5.3 Complexity of Programs 298
5.3.1 Counting Statements 300
5.3.2 Two Algorithms Illustrating Selection 302
5.3.3 An Algorithm Illustrating Repetition 304
5.3.4 An Algorithm Illustrating Nested Repetition 307
5.3.5 Time Complexity of an Algorithm 308
5.3.6 Variants on the Definition of Complexity 311
5.4 Exercises 313
5.5 Uncomputability 316
5.5.1 The Halting Problem 318
5.6 Chapter Review 321
5.6.1 Summary 321
5.6.2 Starting to Review 322
5.6.3 Review Questions 322
5.6.4 Using Discrete Mathematics in Computer Science 323