Cam's Cyberspace

Recent Notes

Divide and Conquer

6 min read

Overview

Divide and conquer (D&C) is a strategy that solves a problem by splitting it into smaller instances, recursively solving those, then combining the subresults into a full solution. Its performance often follows a recurrence such as T(n) = a·T(n/b) + f(n), analyzable by recursion trees and the Recurrences: Master Theorem. Many foundational algorithms—Merge Sort, closest-pair of points, Karatsuba multiplication, and Strassen matrix multiplication—are D&C designs.

Motivation

Large problems can be expensive to tackle directly, but structure repeats at smaller scales. By isolating subproblems and combining them, D&C achieves:

  • Asymptotic improvements (e.g., O(n log n) sorting vs O(n²)).

  • Parallelism: independent subcalls can run concurrently.

  • Locality: subproblems fit in cache, improving constant factors.

  • Composability: the same pattern generalizes across domains (arrays, geometry, algebra, graphs).

When subproblems overlap heavily or the combine step must reason about past choices, prefer Dynamic Programming. When a local rule provably leads to the global optimum, use Greedy Algorithms.

Definition and Formalism

A D&C algorithm specifies:

  • Divide: Map instance size n into a subproblems, each of size about n/b (not necessarily equal).

  • Conquer: Solve subproblems recursively. Base cases (n ≤ n₀) are solved directly.

  • Combine: Produce the full solution from subresults in time f(n).

The running time often satisfies T(n) = a·T(⌈n/b⌉) + f(n), with T(n)=Θ(1) for n≤n₀.

Typical analysis tools:

  • Recursion tree: visualize total work per depth and sum across O(log_b n) levels.

  • Master theorem: compare f(n) to n^{log_b a} to obtain T(n) asymptotics.

  • Akra–Bazzi (generalized): handle uneven splits or additive offsets.

Tip

Align subproblem boundaries carefully. For arrays, prefer half-open ranges A[l..r) with m = l + (r - l)/2 to avoid off-by-one and overflow.

Example or Illustration

Canonical skeleton (array interval)

function SOLVE(A, l, r):               // solves on half-open interval [l, r)
    if r - l <= BASE: return BASE_SOLVE(A, l, r)
    m = l + (r - l) / 2
    left  = SOLVE(A, l, m)
    right = SOLVE(A, m, r)
    return COMBINE(left, right, A, l, m, r)

Merge sort (work-balanced, combine-heavy)

  • Divide: split array in halves.

  • Conquer: recursively sort halves.

  • Combine: merge in linear time. Recurrence: T(n)=2T(n/2)+Θ(n) ⇒ Θ(n log n).

Closest pair of points (2D geometry)

  • Divide: split by median x.

  • Conquer: solve left/right subsets.

  • Combine: consider only points within δ of the split and check a constant number of neighbors after sorting by y. Recurrence: T(n)=2T(n/2)+Θ(n) ⇒ Θ(n log n) but with subtle constant-factor geometry.

Karatsuba multiplication (fewer subproblems)

  • Divide: split numbers into high/low halves.

  • Conquer: compute 3 half-size products instead of 4.

  • Combine: recombine with additions/shifts. Recurrence: T(n)=3T(n/2)+Θ(n) ⇒ Θ(n^{log₂3}) ≈ Θ(n^{1.585}).

Properties and Relationships

  • Balance vs cost: Increasing a or reducing b increases subcalls; increasing f(n) burdens the combine step. Good designs minimize the dominant term.

  • Depth: With equal-sized splits, depth is O(log_b n), useful for reasoning about parallel span.

  • Cache behavior: Smaller subproblems reuse cache lines, often outperforming naive O(n²) scans even when both are asymptotically inferior/superior on paper.

  • Tailoring base cases: Replacing recursion at small sizes with a fast base algorithm (e.g., Insertion Sort inside merge sort) improves constants without changing big-O.

Links to other paradigms

  • DP vs D&C: D&C assumes independent subcalls; DP handles overlap by memoization/tabulation.

  • Greedy vs D&C: Greedy avoids recursion when an exchange argument applies; without it, D&C (or DP) is safer.

  • Graph view: Many D&C recurrences correspond to solving on a tree/DAG of subproblems; see Recursion for traversal patterns.

Implementation or Practical Context

1) Choosing a split.

  • Even halves (arrays, matrices) simplify reasoning and are cache-friendly.

  • Median-based splits (geometry) keep subproblem sizes balanced even on adversarial inputs.

  • Problem structure may suggest multi-way splits (e.g., quadtrees/octrees).

2) Combine design.

  • Aim for linear (or nearly linear) combine work: e.g., merging two sorted lists, linear-time strip checks in geometry, efficient recombination in algebraic algorithms.

  • When combine is expensive, consider rephrasing the problem to push work downward (do more during subcalls, less at the root).

3) Base case & thresholds.

  • Use an empirically tuned cutoff BASE to switch to a simpler algorithm (e.g., insertion sort for small arrays).

  • Guarantee correctness across the threshold—ensure combine expects the base-case postconditions (e.g., “subarrays are sorted”).

4) Parallelization.

  • Subcalls are good fork–join candidates. Control parallel granularity: spawn tasks only when r-l is large enough to amortize overhead.

  • Combine steps (merging, reductions) can themselves be parallelized with careful partitioning.

5) Memory layout.

  • Prefer in-place or buffer-reusing designs to constrain auxiliary space (e.g., alternating buffers for merges).

  • Be mindful of stack depth; for n large, either ensure O(log n) recursion or convert to an explicit stack.

6) Debuggability.

  • Log intervals [l,r) and invariants at function entry/exit.

  • Unit-test: randomized small cases, then adversarial patterns (sorted, reverse-sorted, all equal).

Tip

For numeric problems (FFT-like, multiplication), verify combine identities symbolically on small sizes (property tests). Algebraic mistakes hide easily behind fast asymptotics.

Common Misunderstandings

Warning

Overlapping subproblems assumed independent. If subcalls share heavy overlap and you recompute them, complexity can explode; redesign as DP or memoize.

Warning

Off-by-one at boundaries. Incorrect mid computation ((l+r)/2 overflow; inclusive ranges) causes missed elements or infinite recursion. Use l + (r-l)/2, and half-open intervals.

Warning

Combine too slow. A quadratic combine wipes out the benefits of splitting; rework invariants so combine is linear or near-linear.

Warning

Unbounded recursion depth. Skewed splits (e.g., a=1, b≈1) can lead to Θ(n) depth and stack overflows; cap depth or rebalance the split.

Broader Implications

D&C underlies:

  • Sorting and selection: merge sort, quickselect (hybrid of partitioning and recursion).

  • Geometry: kd-trees, closest pair, range searching.

  • Linear algebra: Strassen/Winograd, block matrix ops.

  • Signal processing: FFT as a radix-2 (or mixed-radix) divide and conquer over DFTs.

  • Numerical methods: multigrid V-cycles are D&C at multiple resolutions.

  • Parallel and external-memory algorithms: hierarchical decomposition enables work/span bounds and I/O-efficient layouts.

The mindset—isolate substructure, process locally, combine globally—translates to software design (modules) and systems engineering (sharding, map–reduce frameworks).

Summary

Divide and conquer turns large problems into manageable subproblems, solved recursively and stitched together by an efficient combine step. Its performance is captured by recurrences, typically yielding Θ(n log n) or better when subproblems are balanced and combination is linear. Practical success relies on clean boundaries, a fast combine, tuned base cases, and, when available, parallel execution.

See also

Graph View

Backlinks