18. Algorithm Analysis

Prerequisite Information

This chapter assumes that the reader is already familiar with Java Programming and has a strong foundation in the mathematical prerequisites.

Help and Feedback

If you have any questions as you are working through the chapter, you are encouraged to post on the course Piazza page. Your questions will not only help you fill gaps in your knowledge but also give the authors and instructors insight on potential updates to the chapter.

Chapter Contents

• 18.1. Introduction
• 18.2. Algorithm Analysis Steps
  • 18.2.1. Step 1: Defining the Problem Size
  • 18.2.2. Step 2: Identify the Key Processing Steps
  • 18.2.3. Step 3: Analyze the Time Complexity
• 18.3. Example Problems
• 18.4. Space Complexity Analysis
  • 18.4.1. Example Problems
• 18.5. Big-O
  • 18.5.1. Motivation
  • 18.5.2. Symbols and Notation
  • 18.5.3. Informal Definition of Big-O
  • 18.5.4. Notable Big-O Sets
  • 18.5.5. Proving a Function is in a Big-O Set
    • 18.5.5.1. Example 1: \(T(n) = 2n^2 + 3n − 2\) is in \({\rm O}(n^2)\)
    • 18.5.5.2. Example 2: \(T(n) \leq 3n^2 + 39\) is in \({\rm O}(n^2)\)
    • 18.5.5.3. Example 3: \(T(n) = n^3 + 2\log_4(n) + 6\) is in \({\rm O}(n^3)\)
    • 18.5.5.4. Example 4: \(T(n) = 42\) is in \({\rm O}(1)\)
    • 18.5.5.5. Example 5: \(T(n) = n^2 + 1\) is in \({\rm O}(n^2)\) and \({\rm O}(n^3)\)
  • 18.5.6. Nested Big-O Sets
  • 18.5.7. Quick Big-O Derivation
  • 18.5.8. Logarithm Base in Big-O
  • 18.5.9. Algorithm Examples
  • 18.5.10. Appendix
    • 18.5.10.1. Formal Definition of Big-O
    • 18.5.10.2. Other Bounds