3. Chapter 03: Complexity of Algorithms and Order Notation

• 3.1. Generating Arrays
  • 3.1.1. Simple random generators
  • 3.1.2. Measuring execution time
  • 3.1.3. Randomised array generation and testing
• 3.2. Complexity of Algorithms
• 3.3. Order Notation
  • 3.3.1. Big O-notation
  • 3.3.2. Properties of Big O-notation
  • 3.3.3. Little o-notation
  • 3.3.4. Proofs using O-notation
  • 3.3.5. Hierarchy of algorithm complexities
  • 3.3.6. Complexity of sequential composition
• 3.4. Sums of Series and Complexities of Loops
  • 3.4.1. Arithmetic series
  • 3.4.2. Geometric series
  • 3.4.3. Estimating a sum by an integral
  • 3.4.4. Big O and function composition
  • 3.4.5. Complexity of algorithms with loops
• 3.5. Complexity of Simple Recursive Algorithms
  • 3.5.1. Complexity of computing the factorial
  • 3.5.2. Method of differences
  • 3.5.3. Recurrence relations
  • 3.5.4. First-order recurrence relations
  • 3.5.5. Inhomogeneous recurrence relations
• 3.6. Exercises
  • 3.6.1. Exercise 1: Realistic Complexity of Laplace Expansion
  • 3.6.2. Exercise 2
  • 3.6.3. Exercise 3