Level 3 · 45 min

Divide & Conquer + the Master Theorem

Divide and conquer splits a problem into smaller independent subproblems, solves them, and combines their results. The Master Theorem is a shortcut for reading the recurrence when the split is regular.

Three phases: divide, solve, combine

Merge sort divides the array in half, recursively sorts each half, then merges in linear time. Binary search divides into one half and combines in constant time. The algorithm design question is whether the subproblems are independent and smaller enough to pay for the overhead.

Reading T(n) = a T(n/b) + f(n)

The recurrence compares recursive work with non-recursive work. a is the number of subproblems, n/b is subproblem size, and f(n) is divide plus combine. For merge sort, a = 2, b = 2, f(n) = n, so total work is Theta(n log n).

When the theorem does not apply

The Master Theorem assumes regular subproblem sizes and polynomial-like combine work. It does not directly handle uneven splits, overlapping subproblems, or recurrences with messy floors and ceilings. In those cases, use recursion trees, substitution, or transform the recurrence.

Key Takeaways

Divide and conquer pays off when subproblems are independent and combine cost is controlled.
The Master Theorem compares leaf-level recursive work with per-level combine work.
Overlapping subproblems are a DP smell, not a pure divide-and-conquer fit.

Code example

function mergeSort(items):
  if length(items) <= 1:
    return items
  mid = floor(length(items) / 2)
  left = mergeSort(items[0:mid])
  right = mergeSort(items[mid:end])
  return merge(left, right)