• What is Divide and Conquer?
• Master Theorem and Recurrences
• Classic Algorithms
• Techniques and Optimizations
• Implementation Patterns
• Exercises

Divide and conquer splits a problem into subproblems, solves them (often recursively), and combines their solutions. It shines when subproblems are similar and the combine step is efficient.

• Structure: divide → conquer → combine
• Complexity: typically expressed by a recurrence T(n) = a T(n/b) + f(n)
• Examples: mergesort, quicksort, Karatsuba, FFT, closest pair of points

Master theorem for T(n) = a T(n/b) + f(n):
- Let n^{log_b a} be the critical term.
Case 1: if f(n) = O(n^{log_b a - ε}) → T(n) = Θ(n^{log_b a})
Case 2: if f(n) = Θ(n^{log_b a} log^k n) → T(n) = Θ(n^{log_b a} log^{k+1} n)
Case 3: if f(n) = Ω(n^{log_b a + ε}) and regularity holds → T(n) = Θ(f(n))

Use Akra–Bazzi for unbalanced splits or additive shifts, e.g., T(n) = T(n/2) + T(n/3) + n.

• Mergesort: a = 2, b = 2, f(n) = Θ(n) → Θ(n log n)
• Quicksort (average): a = 2, b = 2, f(n) = Θ(n) → Θ(n log n); worst Θ(n^2)
• Karatsuba multiplication: a = 3, b = 2, f(n) = Θ(n) → Θ(n^{log_2 3}) ≈ Θ(n^{1.585})
• Strassen matrix multiply: a = 7, b = 2, f(n) = Θ(n^2) → Θ(n^{log_2 7}) ≈ Θ(n^{2.807})
• Closest pair of points: divide plane, merge in strip → Θ(n log n)
• FFT/NTT: a = 2, b = 2, f(n) = Θ(n) with structured combine → Θ(n log n)

• Conquer efficiently: aim for linear-time combine steps.
• Divide cleverly: equal-sized subproblems simplify analysis and cache behavior.
• Divide-and-lift: use recursion to precompute and push info upward (e.g., segment trees).
• Cache locality: recursive divide improves locality over naive loops.
• Parallelism: independent subproblems can be parallelized.

// Mergesort (stable)
function mergeSort(a) {
  if (a.length <= 1) return a.slice();
  const m = a.length >> 1;
  const L = mergeSort(a.slice(0, m));
  const R = mergeSort(a.slice(m));
  const out = [];
  let i = 0, j = 0;
  while (i < L.length && j < R.length) {
    if (L[i] <= R[j]) out.push(L[i++]); else out.push(R[j++]);
  }
  while (i < L.length) out.push(L[i++]);
  while (j < R.length) out.push(R[j++]);
  return out;
}

1. Implement closest pair of points in O(n log n).
2. Show the Master theorem application for Strassen’s algorithm.
3. Derive the recurrence and solve for Karatsuba’s algorithm.