vault

Divide and Conquer Paradigm

19 min read

Divide and Conquer Paradigm

Divide and conquer (D&C) is one of the four foundational algorithm-design paradigms taught in every introductory algorithms course alongside greedy, dynamic programming, and backtracking. Its recipe is universal and short: (1) divide the problem into smaller sub-problems of the same kind, (2) conquer each sub-problem by recursive application of the same algorithm (or solve directly when small enough), (3) combine the sub-solutions into a solution for the original problem. The technique dates back at least to John von Neumann’s 1945 description of merge sort in the First Draft of a Report on the EDVAC — the first divide-and-conquer algorithm in modern computer science. The paradigm’s mathematical signature is a recurrence relation of the form T(n) = a · T(n/b) + f(n), solved by the Master Theorem (or, for non-uniform sub-problem sizes, by the Akra-Bazzi method). D&C wins decisively when (a) the problem decomposes naturally into independent sub-problems of the same structural form, (b) the combine step is asymptotically cheap relative to the conquer step, and (c) the sub-problems do not overlap. When sub-problems overlap, we are in dynamic programming territory and should memoize. When the combine step does all the work, we have a degenerate recurrence and gain nothing. Canonical D&C algorithms include Merge Sort (T(n) = 2T(n/2) + Θ(n) → Θ(n log n)), Quicksort (same recurrence on average), Binary Search (T(n) = T(n/2) + Θ(1) → Θ(log n)), Karatsuba Multiplication (T(n) = 3T(n/2) + Θ(n) → Θ(n^{log₂ 3})), Strassen’s Algorithm (T(n) = 7T(n/2) + Θ(n²) → Θ(n^{log₂ 7})), FFT (T(n) = 2T(n/2) + Θ(n) → Θ(n log n)), and Closest Pair of Points (T(n) = 2T(n/2) + Θ(n) → Θ(n log n)). The paradigm’s deeper conceptual significance: it exposes the structure of a problem by repeated halving, making latent regularities visible. Many D&C algorithms (Karatsuba, Strassen, FFT) achieve sub-quadratic complexity precisely because divide-and-conquer reveals an algebraic identity that lets the combine step do fewer sub-problems than the obvious approach.

1. Intuition — The Three-Step Recipe

The paradigm is captured in three lines:

divide_and_conquer(problem):
    if problem is small enough:
        return base_case_solution(problem)            # CONQUER (base case)

    sub_problems := divide(problem)                   # DIVIDE
    sub_solutions := [
        divide_and_conquer(s) for s in sub_problems   # CONQUER (recursion)
    ]
    return combine(sub_solutions)                     # COMBINE

A real-world analogy: imagine sorting a deck of 1000 playing cards. Sorting all 1000 at once is unwieldy. So you divide the deck in half, give each half to a friend, and ask each friend to sort their 500 cards (recursion!). When they hand back two sorted halves, you merge them — you have two sorted piles and you repeatedly take the smaller top card and place it in the output pile. The merge takes 1000 comparisons (linear in deck size). The total work, modulo recursion overhead, is 1000 · log₂ 1000 ≈ 10,000 comparisons — versus the ~500,000 of the naive Θ(n²) insertion sort. This is Merge Sort, and it’s the prototypical D&C win.

The paradigm’s effectiveness depends on three structural properties of the problem:

  1. Self-similar decomposition. The sub-problems must be instances of the same problem type. Sorting 500 cards is the same kind of problem as sorting 1000. This is the “recursion-friendly” structure.
  2. Independence. The sub-problems must be solvable without consulting one another. If the answer to one sub-problem depends on the answer to another, you’ve left D&C territory.
  3. Cheap combine. The combine step must be fast enough that it doesn’t dominate. If combining two sub-solutions costs as much as solving them from scratch, the divide step gained you nothing.

When all three hold, D&C is often the natural algorithm — and frequently the asymptotically optimal one.

2. The Master Theorem Lens

Most D&C recurrences have the form

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

where a ≥ 1 is the number of sub-problems, b > 1 is the size-shrinkage factor (each sub-problem is 1/b-th the size of the parent), and f(n) is the combine cost.

The Master Theorem classifies the asymptotics by comparing f(n) against n^{log_b a} (the work done at the leaves):

  • Case 1 — leaf-heavy. If f(n) = O(n^{log_b a − ε}) for some ε > 0, the leaves dominate and T(n) = Θ(n^{log_b a}). The combine is asymptotically irrelevant — almost all the work is at the bottom of the recursion. Examples: Karatsuba (a=3, b=2, f(n)=O(n), n^{log₂ 3} = n^{1.585} dominates) and Strassen (a=7, b=2, f(n)=O(n²), n^{log₂ 7} = n^{2.807} dominates).
  • Case 2 — balanced. If f(n) = Θ(n^{log_b a} · log^k n) for k ≥ 0, work is balanced across levels and T(n) = Θ(n^{log_b a} · log^{k+1} n). Examples: Merge Sort (a=2, b=2, f(n)=Θ(n) = Θ(n^{log₂ 2}), gives Θ(n log n)) and Binary Search (a=1, b=2, f(n)=Θ(1) = Θ(n^{log₂ 1}) = Θ(1), gives Θ(log n)).
  • Case 3 — root-heavy (combine-heavy). If f(n) = Ω(n^{log_b a + ε}) and the regularity condition a · f(n/b) ≤ c · f(n) for some c < 1 holds, the root dominates and T(n) = Θ(f(n)). Example: a recurrence like T(n) = 2T(n/2) + Θ(n²) gives T(n) = Θ(n²) because the linear-quadratic combine swamps the leaf work.

The Master Theorem fails when sub-problem sizes are non-uniform (e.g., T(n) = T(n/3) + T(2n/3) + Θ(n)); the Akra-Bazzi method (Akra & Bazzi, 1998) generalizes to such cases.

3. When D&C Wins, When It Loses

3.1 D&C Wins (3 + 1 conditions)

D&C is the right hammer when:

  1. The problem decomposes naturally. Sorting decomposes into “sort halves and merge”; convex-hull computation decomposes into “compute hulls of halves and merge”; matrix multiplication decomposes into block multiplications.
  2. Sub-problems are independent. No shared state between siblings.
  3. Combine is asymptotically cheap. Often O(n) or O(n log n). If f(n) = Θ(n^{log_b a}), you’re balanced (Case 2) and pay a log n premium; if f(n) = O(n^{log_b a − ε}) you’re leaf-heavy (Case 1) and the combine is free asymptotically.
  4. There’s an algebraic identity that reduces the number of sub-problems below the obvious count. This is the deeper structural win — Karatsuba (4 → 3), Strassen (8 → 7), FFT (n² → n log n via roots of unity). The “obvious” naive D&C with no identity often gives the same asymptotic as the iterative naive algorithm; the win comes from the identity.

3.2 D&C Loses

D&C is the wrong hammer when:

  1. Sub-problems overlap. The same sub-problem is solved many times. Example: naive recursion for the n-th Fibonacci number computes F(n−2) once for F(n) and again for F(n−1), doubling at every level — exponential time. The fix is dynamic programming: cache sub-solutions and reuse them. The general rule: if the same sub-problem appears in multiple branches of the recursion tree, switch to DP.
  2. Combine is as expensive as the original problem. If solving two halves and merging them costs Θ(n²), you haven’t reduced anything compared to a direct Θ(n²) algorithm. Example: a naive recurrence T(n) = 2T(n/2) + Θ(n²) gives Θ(n²) — same as not bothering with D&C.
  3. The base case is trivial but the recursion overhead dominates. For very small n, the function-call overhead, allocation, and stack pushes of recursion can dwarf the asymptotic savings. Production sorts like Tim Sort and Intro Sort use insertion sort below n ≈ 16 precisely because the constant factors of insertion sort are smaller for tiny arrays.
  4. The problem is inherently sequential. Problems with strict left-to-right data dependencies (e.g., processing a stream where each element depends on all previous elements’ aggregated state) resist D&C. You can’t process the second half until you’ve finished the first half.

3.3 D&C vs Backtracking vs DP

ParadigmWhenAsymptoticCommon signature
D&CIndependent sub-problems, cheap combineT(n) = a T(n/b) + f(n)Master Theorem
DPOverlapping sub-problems, optimal substructureT(n) = Σ T(sub) + Θ(combine) with memoizationPolynomial-time solution to NP-style brute force
BacktrackingSearch through exponential space with pruningT(n) = O(b^d) with branching b, depth dConstraint satisfaction (N-Queens, Sudoku)
GreedyLocally optimal choice yields global optimumT(n) = Θ(n log n) typicallyMatroids, exchange argument

The relationships are tight. DP is “D&C with caching for overlapping sub-problems.” Backtracking is “D&C plus pruning when the sub-problems are search nodes with constraints.” Greedy is a special case where the divide step makes a single irrevocable choice.

4. Tiny Worked Example — Counting Inversions

An inversion in an array is a pair (i, j) with i < j but A[i] > A[j]. Counting inversions naively is Θ(n²). D&C gives Θ(n log n) — the algorithm is a small modification of Merge Sort.

The recipe:

  1. Divide the array in half.
  2. Conquer by recursively counting inversions in each half.
  3. Combine by counting “cross-inversions” (pairs where one element is in the left half, the other in the right) during a modified merge step. Whenever, in the merge, an element from the right half is placed before some elements still pending in the left half, all those pending left elements are larger, so each contributes one inversion.

Example: A = [2, 4, 1, 3, 5].

Divide: L = [2, 4], R = [1, 3, 5].

Recurse:

  • inversions(L) = 0 (already sorted).
  • inversions(R) = 0 (already sorted).

Combine — merge L and R:

  • Compare 2 and 1: 1 < 2, so place 1. Pending L = [2, 4] (2 elements). Cross-inversions += 2.
  • Compare 2 and 3: 2 < 3, so place 2. Pending L = [4] (1 element).
  • Compare 4 and 3: 3 < 4, so place 3. Pending L = [4]. Cross-inversions += 1.
  • Compare 4 and 5: 4 < 5, so place 4. Pending L = [].
  • Place remaining 5.

Cross-inversions = 2 + 1 = 3. Total inversions = 0 + 0 + 3 = 3.

Verify by enumeration: pairs (2, 1), (4, 1), (4, 3) — exactly 3 inversions. ✓

The recurrence: T(n) = 2 T(n/2) + Θ(n) (merge is O(n)), giving Θ(n log n) by Master Theorem Case 2.

5. Pseudocode — Generic D&C Skeleton

divide_and_conquer(problem):
    # Base case — handle small problems directly.
    if size(problem) <= base_case_threshold:
        return solve_directly(problem)

    # Divide — split into a sub-problems each of size n / b.
    sub_problems := divide(problem)              # |sub_problems| = a, each size n/b

    # Conquer — recursively solve each sub-problem.
    sub_solutions := [divide_and_conquer(sp) for sp in sub_problems]

    # Combine — assemble the sub-solutions into a global solution.
    return combine(sub_solutions, problem)       # O(f(n)) work

Concrete instantiations:

AlgorithmabdividecombineRecurrenceAsymptotic
Merge Sort22split in halvesmerge two sorted halves O(n)T(n) = 2 T(n/2) + Θ(n)Θ(n log n)
Quicksort (average)22partition around pivotconcatenate (free)T(n) = 2 T(n/2) + Θ(n)Θ(n log n)
Binary Search12half the arraytrivialT(n) = T(n/2) + Θ(1)Θ(log n)
Karatsuba Multiplication32high/low halveslinear add/sub Θ(n)T(n) = 3 T(n/2) + Θ(n)Θ(n^{1.585})
Strassen’s Algorithm724 quadrants18 block adds Θ(n²)T(n) = 7 T(n/2) + Θ(n²)Θ(n^{2.807})
FFT — Fast Fourier Transform22even/odd indicescombine via twiddles Θ(n)T(n) = 2 T(n/2) + Θ(n)Θ(n log n)
Closest Pair of Points22split by median xstrip merge Θ(n)T(n) = 2 T(n/2) + Θ(n)Θ(n log n)
Maximum Subarray (CLRS §4.1)22halvescrossing-max Θ(n)T(n) = 2 T(n/2) + Θ(n)Θ(n log n) (improvable to Θ(n) via Kadane’s Algorithm)

6. Python — Generic D&C Template + Counting Inversions

from typing import Callable, TypeVar
 
T = TypeVar('T')          # problem type
S = TypeVar('S')          # solution type
 
 
def divide_and_conquer(
    problem: T,
    *,
    is_base: Callable[[T], bool],
    base: Callable[[T], S],
    divide: Callable[[T], list[T]],
    combine: Callable[[list[S], T], S],
) -> S:
    """Generic divide-and-conquer driver. Pure-Python, recursion-based."""
    if is_base(problem):
        return base(problem)
 
    sub_problems = divide(problem)
    sub_solutions = [
        divide_and_conquer(
            sp,
            is_base=is_base, base=base,
            divide=divide, combine=combine,
        )
        for sp in sub_problems
    ]
    return combine(sub_solutions, problem)
 
 
# ----- Concrete instantiation: count inversions in O(n log n) -----
 
def count_inversions(arr: list[int]) -> tuple[list[int], int]:
    """
    Return (sorted_arr, inversion_count). Modified merge sort:
    every time we 'pull from the right half' during merge, the pending
    elements in the left half are each larger, contributing |left_pending|
    inversions.
    """
    if len(arr) <= 1:
        return arr[:], 0
 
    mid = len(arr) // 2
    left,  inv_l = count_inversions(arr[:mid])
    right, inv_r = count_inversions(arr[mid:])
 
    merged: list[int] = []
    cross = 0
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            # right[j] is smaller than every remaining left[i..end-1]
            # — each contributes one inversion.
            merged.append(right[j])
            cross += len(left) - i
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
 
    return merged, inv_l + inv_r + cross
 
 
# Sanity test
if __name__ == "__main__":
    arr = [2, 4, 1, 3, 5]
    sorted_arr, inv = count_inversions(arr)
    assert sorted_arr == [1, 2, 3, 4, 5]
    assert inv == 3
    print("ok")

The crucial line is cross += len(left) - i — it counts all remaining left-half elements that are larger than the just-placed right[j]. This is the algebraic insight that makes inversion counting O(n log n) instead of O(n²): rather than checking every pair across halves explicitly, the merge step amortizes the count into one update per right-element placed.

7. Common Recurrences and Their Solutions

The set of recurrences that arise from “natural” D&C algorithms is small. Memorize these:

T(n) = T(n/2) + Θ(1)        →  Θ(log n)              [Binary Search]
T(n) = T(n/2) + Θ(n)        →  Θ(n)                  [linear-time selection of one half]
T(n) = 2 T(n/2) + Θ(1)      →  Θ(n)                  [tree traversal-style]
T(n) = 2 T(n/2) + Θ(n)      →  Θ(n log n)            [Merge Sort, Closest Pair, FFT]
T(n) = 2 T(n/2) + Θ(n²)     →  Θ(n²)                 [combine dominates; D&C gains nothing]
T(n) = 3 T(n/2) + Θ(n)      →  Θ(n^{log₂ 3}) ≈ n^{1.585}  [Karatsuba]
T(n) = 4 T(n/2) + Θ(n)      →  Θ(n²)                 [naive D&C matrix mult — same as schoolbook]
T(n) = 7 T(n/2) + Θ(n²)     →  Θ(n^{log₂ 7}) ≈ n^{2.807}  [Strassen]
T(n) = 8 T(n/2) + Θ(n²)     →  Θ(n³)                 [naive D&C matrix mult — same as schoolbook]
T(n) = T(n − 1) + Θ(1)      →  Θ(n)                  [linear recursion, e.g., factorial]
T(n) = T(n − 1) + Θ(n)      →  Θ(n²)                 [insertion sort, naive selection sort]
T(n) = 2 T(n − 1) + Θ(1)    →  Θ(2ⁿ)                 [Tower of Hanoi, naive Fibonacci]
T(n) = T(n/3) + T(2n/3) + Θ(n)  →  Θ(n log n)        [Akra-Bazzi; non-uniform split]

Reading these off becomes second nature after exposure. The pattern: when sub-problem sizes shrink by a constant factor b > 1 and there are a sub-problems, the leaf count is a^{log_b n} = n^{log_b a}, which is the lowest possible asymptotic. Whether the combine work pushes you above that depends on f(n) vs n^{log_b a} — the Master Theorem tells you which dominates.

8. Diagram — The Recursion Tree

flowchart TD
    R["T(n)<br/>combine: f(n)"]

    R --> A1["T(n/b)"]
    R --> A2["T(n/b)"]
    R --> A3["...<br/>(a children)"]
    R --> A4["T(n/b)"]

    A1 --> B11["T(n/b²)"]
    A1 --> B12["T(n/b²)"]
    A1 --> B13["...<br/>(a children)"]

    A4 --> B41["T(n/b²)"]
    A4 --> B42["T(n/b²)"]
    A4 --> B43["..."]

    style R fill:#fed
    style A1 fill:#fea
    style A2 fill:#fea
    style A3 fill:#fea
    style A4 fill:#fea
    style B11 fill:#bfb
    style B12 fill:#bfb
    style B13 fill:#bfb
    style B41 fill:#bfb
    style B42 fill:#bfb
    style B43 fill:#bfb

What this diagram shows. A generic divide-and-conquer recursion tree. The root represents the top-level problem of size n with combine cost f(n). It spawns a child sub-problems, each of size n/b. Each child recursively spawns a grandchildren of size n/b². The tree has branching factor a, depth log_b n, and a^{log_b n} = n^{log_b a} leaves. The total work is the sum over all levels of (number of nodes at this level) × (combine cost per node). This sum has three cases: leaf-heavy (Case 1, f(n) polynomially smaller than n^{log_b a}), balanced (Case 2, equal up to log factors), and root-heavy (Case 3, f(n) polynomially larger). The geometric series defining the sum determines which level dominates and gives the Master Theorem cases.

9. The “Recombination Trick” — Why D&C Beats Iteration

A naive iterative algorithm and a naive D&C algorithm often have the same asymptotic complexity. The asymptotic win of D&C comes when divide-and-conquer exposes an algebraic structure that lets the combine step do less work than the obvious decomposition.

Three paradigm examples:

  1. Karatsuba (1962): Naive multiplication of n-digit integers is Θ(n²). Split each integer at the middle digit; the obvious D&C gives 4 sub-multiplications of half-size, recurrence T(n) = 4T(n/2) + Θ(n) = Θ(n²) — no win. Karatsuba’s identity replaces 4 sub-multiplications with 3 plus extra additions, recurrence T(n) = 3T(n/2) + Θ(n) = Θ(n^{log₂ 3}) — sub-quadratic.
  2. Strassen (1969): Naive matrix multiplication is Θ(n³). Block partition gives 8 sub-multiplications, recurrence T(n) = 8T(n/2) + Θ(n²) = Θ(n³) — no win. Strassen’s identity replaces 8 with 7 plus extra additions, recurrence T(n) = 7T(n/2) + Θ(n²) = Θ(n^{log₂ 7}) — sub-cubic.
  3. FFT (Cooley-Tukey 1965): Naive DFT is Θ(n²). Split by even/odd indices, exploit the algebraic identity that ω^{2k} = (ω²)^k (where ω is the n-th primitive root of unity) to write the size-n DFT as two size-n/2 DFTs plus O(n) combination — recurrence T(n) = 2T(n/2) + Θ(n) = Θ(n log n).

The pattern: D&C is most powerful when the recursion tree’s branching factor a can be reduced below the obvious value via an algebraic identity in the combine step. Without such an identity, naive D&C often gives the same asymptotic as iteration.

10. Pitfalls

  1. Choosing D&C when sub-problems overlap. The classic pitfall: writing fib(n) = fib(n-1) + fib(n-2) and being shocked it takes exponential time. Sub-problems overlap massively. Fix: memoize, turning the recurrence into linear time. The general rule: if a sub-problem can appear in more than one branch of the recursion tree, you need DP, not D&C.
  2. Choosing D&C when the combine step is too expensive. If f(n) = Ω(n^{log_b a + ε}), the combine dominates and D&C reduces to “spend f(n) time at the root, then recurse trivially.” There’s no asymptotic gain. Example: T(n) = 2T(n/2) + Θ(n²) = Θ(n²) — same as a direct Θ(n²) algorithm.
  3. Misapplying the Master Theorem. The theorem requires b > 1 (constant size shrinkage), a ≥ 1, and f(n) polynomially separated from n^{log_b a} for Cases 1 and 3. There are gaps — recurrences where f(n) = Θ(n^{log_b a} · (log n)^{−1}) for instance — that fall through the theorem’s cases and require Akra-Bazzi or first-principles analysis.
  4. Forgetting the regularity condition in Case 3. Master Theorem Case 3 requires a · f(n/b) ≤ c · f(n) for some c < 1. Without this, Case 3 conclusion T(n) = Θ(f(n)) may not hold even when f(n) is polynomially larger than n^{log_b a}.
  5. Recursion overhead on small inputs. D&C recursing all the way to n = 1 pays per-call overhead at every level. Production code uses a threshold base case — when n falls below ~16–64, switch to insertion sort, schoolbook multiplication, or whatever simple algorithm has the smallest constant factor. Tim Sort and Intro Sort both do this.
  6. Stack overflow on deep recursion. Recursion depth is Θ(log n) for D&C — usually well within the default stack limit. But for unbalanced D&C (Quicksort worst case, where one side has n − 1 elements), depth can be Θ(n) and overflow the stack. Mitigations: tail-call optimization (where supported), iterative recursion via explicit stack, or pivot-randomization to avoid the bad case in expectation.
  7. Inefficient divide step. The divide step itself can be expensive. For Merge Sort on a linked list, the divide step (find the middle) is O(n), but only one child is recursed on the head pointer — you must split the list explicitly to avoid one half re-walking the other. Subtle bugs come from sloppy splitting.
  8. Ignoring cache effects. D&C is often very cache-friendly because sub-problems fit in cache once they shrink past the cache size. This is why naive matrix multiplication is much slower than tiled or recursive D&C in practice — even when both are Θ(n³). The asymptotic equivalence hides a 5–10× constant-factor cache advantage for D&C.
  9. Confusing D&C with recursion in general. Recursion is a control structure; D&C is a paradigm. Tree traversals, backtracking, and many DP formulations use recursion but are not D&C — they don’t divide into independent sub-problems of the same kind, or they don’t combine, or they have overlapping sub-problems.
  10. Believing D&C parallelizes for free. It often does, because sub-problems are independent. But the combine step may sequentially depend on all sub-solutions, creating an Amdahl’s-law bottleneck. For Merge Sort, the merge step is sequential O(n); parallel merge sort needs a parallel merge algorithm to achieve theoretical linear speedup.

11. Common Interview Problems

ProblemSourceD&C variant
Merge SortClassicT(n) = 2T(n/2) + Θ(n)
QuicksortClassicT(n) = 2T(n/2) + Θ(n) average
Binary SearchClassicT(n) = T(n/2) + Θ(1)
Karatsuba MultiplicationCLRS Problem 4-3T(n) = 3T(n/2) + Θ(n)
Strassen’s AlgorithmCLRS §4.2T(n) = 7T(n/2) + Θ(n²)
Closest Pair of PointsCLRS §33.4T(n) = 2T(n/2) + Θ(n)
Count InversionsClassicModified merge sort, Θ(n log n)
Maximum SubarrayLeetCode 53; CLRS §4.1D&C Θ(n log n); Kadane Θ(n)
Median of Two Sorted ArraysLeetCode 4Binary-search-style D&C, Θ(log(m+n))
Construct Binary Tree from Inorder + PreorderLeetCode 105D&C on subarrays
Different Ways to Add ParenthesesLeetCode 241Recursive split + combine
Skyline ProblemLeetCode 218D&C merge of skyline halves, Θ(n log n)
Reverse PairsLeetCode 493Modified merge sort, Θ(n log n)
Burst BalloonsLeetCode 312Interval DP — but the paradigm is D&C-flavor

12. Open Questions

  • Is there a problem where D&C achieves a strictly better asymptotic than is achievable by any iterative or DP algorithm? Conjecturally yes for many problems (e.g., matrix multiplication’s Θ(n^{2.371…}) is currently achievable only via algebraic D&C-flavored algorithms), but lower bounds are notoriously hard.
  • How does cache-oblivious D&C (Frigo et al. 1999) interact with the Master Theorem? Cache-oblivious D&C achieves optimal cache complexity for a wide class of problems without knowing the cache size in advance — a beautiful result built atop the D&C paradigm.
  • When does the Akra-Bazzi method give a tighter bound than the Master Theorem? Always, on Master-Theorem-amenable inputs they agree; Akra-Bazzi additionally handles non-uniform splits and non-polynomial f(n).
  • Can D&C be combined with DP in a hybrid? Yes — divide-and-conquer DP is a class of optimizations (Knuth’s optimization, divide-and-conquer DP optimization for dp[i][j] = min_{k} dp[i-1][k] + cost(k, j) with quadrangle inequality) that exploit monotonicity to drop a O(n) factor from a 2D DP. See Knuth’s Optimization (planned).
  • Why does the Master Theorem work with constant b but not when sub-problem sizes are non-constant? The proof requires the geometric series in n / b^k to be well-behaved; non-uniform splits break the simple geometric structure and require Akra-Bazzi’s integral-based machinery.

13. See Also

Graph View

Backlinks