Skip to main content

Divide and Conquer

Divide and conquer splits a problem into smaller instances of the same form, solves them independently, and combines their results.

Three obligations​

  1. Divide: define subproblems and show their sizes shrink.
  2. Conquer: solve base cases and recurse on each subproblem.
  3. Combine: construct the parent solution and account for its cost.

A common runtime recurrence is

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

where aa is the number of subproblems, each has size about n/bn/b, and f(n)f(n) covers partitioning and combination. The recursion tree, substitution, or the Master Theorem can solve suitable recurrences; irregular sizes and dependencies may require other methods.

Representative patterns​

  • Merge sort: two half-size sorts plus a linear merge, yielding Θ(nlog⁡n)\Theta(n\log n).
  • Quicksort: linear partition plus input-dependent subproblem sizes.
  • Binary search: one half-size subproblem plus constant combine work.
  • Closest pair and Karatsuba multiplication: the combine strategy is the key improvement over direct enumeration.

Simply splitting an algorithm does not improve it. The subproblem solutions and combine step must solve the original problem, and their recurrence must actually have a better bound.

Boundary with dynamic programming​

Divide-and-conquer subproblems are usually independent. Heavy overlap causes repeated work and suggests memoization or dynamic programming. Conversely, both styles can use recursion; syntax does not determine the design technique.

Independent branches may run in parallel, but practical speedup is bounded by the critical path, combine work, scheduling, communication, and memory traffic.

Source​