Divide & Conquer

Master Theorem, Recurrence Relations, Matrix Multiplication

Matrix Multiplication

Key Concepts:

  • Standard Algorithm: O(n³) time - three nested loops
  • Divide & Conquer: Split matrices into submatrices
  • Naive D&C: Still O(n³) - T(n) = 8T(n/2) + O(n²)
  • Key Idea: Reduce number of recursive multiplications

Strassen's Algorithm

Key Concepts:

  • Innovation: Reduces 8 multiplications to 7 using clever additions
  • Time Complexity: O(n^2.81) - better than O(n³)
  • Recurrence: T(n) = 7T(n/2) + O(n²)
  • Trade-off: More additions/subtractions, but fewer multiplications

Video Recommendations:

🎥 Abdul Bari - Strassen's Matrix Multiplication (20 min)

Focus:

Know WHY Strassen is faster (7 vs 8 multiplications) and how to apply Master Theorem to analyze it. You likely won't need to memorize the exact 7 formulas.

Solving Recurrences - Substitution Method

Key Concepts:

  • Process: (1) Guess the solution, (2) Prove by induction
  • Guess Strategies: Use recursion tree or Master Theorem as guide
  • Induction: Assume true for smaller values, prove for n
  • Common Pattern: Prove T(n) ≤ c·f(n) for some constant c

Video Recommendations:

🎥 MIT OCW - Substitution Method (20 min segment)

Recursion Tree Method

Key Concepts:

  • Visual approach: Draw tree showing recursive calls
  • Each level: Shows work done at that recursion depth
  • Sum all levels: Get total work = solution
  • Steps: (1) Draw tree, (2) Calculate work per level, (3) Sum geometric series

Example: T(n) = 2T(n/2) + n

  1. Root: n work, 2 children of size n/2
  2. Level 1: 2·(n/2) = n work total
  3. Level 2: 4·(n/4) = n work total
  4. Height: log n levels, each with n work
  5. Total: n·log n = O(n log n)

Master Theorem (Most Important!)

For recurrences: T(n) = aT(n/b) + f(n)

  • Compare f(n) with n^(log_b a):
  • Case 1: If f(n) = O(n^(log_b a - ε)) for ε > 0, then T(n) = Θ(n^(log_b a))
  • Case 2: If f(n) = Θ(n^(log_b a)), then T(n) = Θ(n^(log_b a) log n)
  • Case 3: If f(n) = Ω(n^(log_b a + ε)) for ε > 0, AND regularity condition holds, then T(n) = Θ(f(n))
Critical value: n^(log_b a)
For T(n) = aT(n/b) + f(n), calculate log_b(a) first!

Video Recommendations:

🎥 Abdul Bari - Master Theorem (23 min) 🎥 Back to Back SWE - Master Theorem Explained (12 min)

Quick Examples:

  • T(n) = 2T(n/2) + n: a=2, b=2, f(n)=n. log₂2 = 1, n¹=n. Case 2! → O(n log n)
  • T(n) = 4T(n/2) + n: a=4, b=2, f(n)=n. log₂4 = 2, n² > n. Case 1! → O(n²)
  • T(n) = 2T(n/2) + n²: a=2, b=2, f(n)=n². log₂2 = 1, n² > n¹. Case 3! → O(n²)
  • T(n) = 7T(n/2) + n²: a=7, b=2, f(n)=n². log₂7 ≈ 2.81, n^2.81 > n². Case 1! → O(n^2.81)

Master Theorem Limitations:

Doesn't apply to: T(n) = 2T(n/2) + n log n (gap isn't polynomial), or when a < 1, or b ≤ 1.

📊 Complexity Growth Visualization

Input Size (n) Operations O(log n) O(n) O(n log n) O(n²) O(2ⁿ)

Key insight: Notice how quickly O(n²) and O(2ⁿ) grow compared to O(n log n). This is why divide & conquer algorithms like merge sort (O(n log n)) are much better than bubble sort (O(n²)) for large inputs!

🧠 Master Theorem Practice Quiz

Q1: For T(n) = 3T(n/4) + n, what is n^(log_b a)?

A) n
B) n^0.79 (approximately)
C) n²
D) n^3
Correct! a=3, b=4, so log₄3 ≈ 0.79. Therefore n^(log_b a) = n^0.79

Q2: For T(n) = 3T(n/4) + n, which case applies?

A) Case 1
B) Case 2
C) Case 3
D) Master Theorem doesn't apply
Correct! f(n) = n and n^(log₄3) ≈ n^0.79. Since n > n^0.79 polynomially (n = n^1), this is Case 3, so T(n) = Θ(n).

Q3: For T(n) = 8T(n/2) + n², what is the solution?

A) Θ(n²)
B) Θ(n² log n)
C) Θ(n³)
D) Θ(n^4)
Correct! a=8, b=2, log₂8 = 3, so n^(log_b a) = n³. f(n) = n² < n³, so Case 1 applies → T(n) = Θ(n³).

✏️ Interactive Practice: Solve These Step-by-Step

Problem 1: T(n) = 9T(n/3) + n

Step 1: Identify a, b, f(n)

a = 9, b = 3, f(n) = n

Step 2: Calculate n^(log_b a)

log₃9 = 2, so n^(log_b a) = n²

Step 3: Compare f(n) with n^(log_b a)

f(n) = n, n^(log_b a) = n². Since n < n² polynomially, this is Case 1.

Step 4: Apply the case and get final answer

Case 1 applies → T(n) = Θ(n²)
Problem 2: T(n) = 2T(n/4) + √n

Try this one yourself! Click to reveal each step.

a = 2, b = 4, f(n) = √n = n^0.5

log₄2 = 0.5, so n^(log_b a) = n^0.5

f(n) = n^0.5 equals n^(log_b a) = n^0.5

Case 2 applies → T(n) = Θ(n^0.5 log n) = Θ(√n log n)

Master Theorem Cheat Sheet

T(n) = aT(n/b) + f(n)

Step 1: Calculate n^(log_b a)
Step 2: Compare f(n) to n^(log_b a)
Step 3: Apply appropriate case