Divide and Conquer

Explanation

Divide and conquer has three steps: divide (split the problem into smaller subproblems), conquer (solve each subproblem recursively — for sufficiently small subproblems, solve directly as a base case), and combine (merge the subproblem solutions into a solution to the original problem). The key property that makes this work is that the subproblems are independent — unlike dynamic programming, where subproblems overlap. The Master Theorem provides a formula for analyzing divide-and-conquer recurrences. For T(n) = aT(n/b) + O(n^d): if d > log_b(a), complexity is O(n^d); if d = log_b(a), complexity is O(n^d log n); if d < log_b(a), complexity is O(n^(log_b a)). Merge sort: a=2, b=2, d=1 → d=log_b(a)=1, so O(n log n). Binary search: a=1, b=2, d=0 → d=log_b(a)=0, so O(log n). Classic divide-and-conquer algorithms: merge sort (divide array in half, sort each half, merge), quick sort (partition around a pivot, sort each partition), binary search (check midpoint, recurse on half), fast Fourier transform (split polynomial into even/odd terms, solve recursively), closest pair of points (divide points into left/right halves), and Strassen's matrix multiplication (faster than standard O(n³)). Divide and conquer is more than a coding pattern — it's a way of thinking about problems. When you see a problem and ask "can I solve it if I already had the solution for the first half and the second half?", you're thinking divide-and-conquer.

Code Example

// Divide and conquer: merge sort (the canonical example)
// Also demonstrates the combine step's importance

function mergeSort(arr) {
  // Base case: array of 0 or 1 is already sorted
  if (arr.length <= 1) return arr;

  // Divide: split into two halves
  const mid = Math.floor(arr.length / 2);
  const left  = mergeSort(arr.slice(0, mid));  // conquer left
  const right = mergeSort(arr.slice(mid));     // conquer right

  // Combine: merge two sorted halves
  return merge(left, right);
}

// The merge (combine) step is O(n)
// With O(log n) levels of recursion → O(n log n) total

// D&C: max subarray sum (Kadane's is O(n), but D&C shows the pattern)
function maxSubarrayDC(arr, lo = 0, hi = arr.length - 1) {
  if (lo === hi) return arr[lo];
  const mid = Math.floor((lo + hi) / 2);
  const leftMax  = maxSubarrayDC(arr, lo, mid);
  const rightMax = maxSubarrayDC(arr, mid + 1, hi);
  const crossMax = maxCrossing(arr, lo, mid, hi);
  return Math.max(leftMax, rightMax, crossMax);
}

Why It Matters for Engineers

Divide and conquer is the template behind some of the most important algorithms in computer science: fast sorting, fast Fourier transforms (used in audio/video compression, signal processing), and fast matrix multiplication. Understanding the pattern means you can recognize and adapt it to novel problems rather than memorizing each algorithm independently. The Master Theorem for analyzing recurrences is particularly useful in system design: when you see a tree-structured computation (like MapReduce, where the reduce step combines sorted partial results), you can estimate its complexity from the branching factor and combine cost.