Problem Decomposition Strategies

The Core Idea: Reduce, Then Solve

Algorithmic thinking is, at its heart, the art of not solving the problem you were given. Instead, you transform that problem — usually too large or too tangled to attack head-on — into one or more strictly easier instances whose answers can be assembled into the answer you actually want. Decomposition is the lever; recursion, induction, and the asymptotics of $T(n)$ are the machinery that makes the lever safe.

Formally, given a problem instance $P$ of size $n$, we seek a function $\text{decompose}(P) \to \{P_1, P_2, \dots, P_a\}$ producing $a \geq 0$ subproblems each of size strictly smaller than $n$, together with a combining function $\text{combine}(P, \text{ans}_1, \dots, \text{ans}_a) \to \text{ans}$. When $a = 0$, $P$ is a base case whose answer is known directly.

Strategic question. “What is the smallest move I can make on this problem that turns it into a problem I either already know how to solve, or that has the same shape but is strictly easier?”

Almost every classical algorithm — merge sort, binary search, FFT, Dijkstra, Strassen's matrix multiplication, dynamic programming over a DAG — is the answer to that question for some specific $P$. The strategies below are the recurring shapes the answer takes.

The Five Decomposition Strategies

Decomposition strategies are not disjoint — many real algorithms are hybrids — but each captures a distinct structural insight. The characteristic differences are: how many subproblems are produced, how much smaller they are, whether they overlap, and whether the input itself must first be transformed.

1. Divide and Conquer

Split the input into $a \geq 2$ independent pieces, recursively solve each, then merge. The hallmark is independence: subproblem answers do not depend on one another, so the recursive calls can in principle run in parallel. Merge sort splits an array of size $n$ into halves of size $n/2$ and merges them in linear time, yielding $T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n)$. The Fast Fourier Transform splits a length-$n$ signal into even-indexed and odd-indexed halves, recurses, and combines with twiddle factors in $\Theta(n)$. Strassen multiplies two $n \times n$ matrices using 7 recursive multiplications of half-sized matrices instead of the naive 8, giving $\Theta(n^{\log_2 7}) \approx \Theta(n^{2.807})$.

2. Decrease and Conquer

Make the problem one step smaller — reduce by a constant (usually 1), or by a constant factor. There is exactly one recursive call. Binary search shrinks the candidate range by half each step (decrease by factor); the Euclidean algorithm replaces $\gcd(a, b)$ with $\gcd(b, a \bmod b)$, decreasing by a variable but provably $O(\log \min(a,b))$ factor; insertion sort sorts $A[0..n-1]$ by sorting $A[0..n-2]$ and inserting $A[n-1]$ in place (decrease by 1).

3. Transform and Conquer

Don't shrink the input — change its representation so that the original problem becomes easy. Three sub-flavors:

1. Instance simplification — presort, then run a simpler algorithm. Finding the median of a sorted array is $O(1)$.
2. Representation change — heapsort first builds a binary heap from the input array ($O(n)$), then repeatedly extracts the max ($O(\log n)$ each). The tree-shaped heap turns “find max” from a linear scan into a constant-time peek.
3. Problem reduction — map your problem to one with a known solver. Counting inversions reduces to a tweaked merge sort; shortest-path on a DAG reduces to topological order plus relaxation; maximum-flow reduces to linear programming.

4. Brute Force / Exhaustive Search

Enumerate every candidate solution and test each. Almost always suboptimal, but invaluable as: a baseline for measuring speedups; a correctness oracle for randomized testing of optimized algorithms; the only known approach for many NP-hard problems at small $n$ (e.g., the traveling salesman with $n \leq 20$). The decomposition is trivial — “try this candidate, then try the rest” — but the candidate space has size $2^n$, $n!$, or worse.

5. Dynamic Programming / Memoization

Use this when subproblems overlap — that is, when a naive recursion would solve the same subproblem an exponential number of times. The naive recursive Fibonacci $F(n) = F(n-1) + F(n-2)$ recomputes $F(n-2)$ twice, $F(n-3)$ three times, and $F(k)$ roughly $\phi^{n-k}$ times where $\phi \approx 1.618$. Caching each subproblem the first time it's solved collapses the exponential tree into a DAG of size $O(n)$. The same trick rescues longest common subsequence ($O(nm)$), edit distance, knapsack, matrix-chain multiplication, and the Bellman equation in reinforcement learning.

The Decomposition Tree

Every recursive decomposition induces a tree: the root is the original problem, the children of any node are the subproblems produced by $\text{decompose}$, and the leaves are base cases. The shape of this tree is the geometry of the algorithm.

The total cost of an algorithm is $\sum_{\text{nodes}} \text{work-at-that-node}$. Equivalently, $\text{depth} \times \text{work-per-level}$ when work is uniform across a level. Merge sort has depth $\log_2 n$ and $\Theta(n)$ work per level → $\Theta(n \log n)$. A naive recursive Fibonacci has depth $n$ and a roughly doubling number of nodes per level → $\Theta(\phi^n)$.

Recurrences: The Algebra of Decomposition

A recurrence is an equation (or inequality) that expresses the running time of a recursive algorithm on input of size $n$ in terms of its running time on smaller inputs. It is the algebraic form of the decomposition tree.

The most-cited general form is the divide-and-conquer recurrence:

$\quad T(n) \;=\; a \cdot T(n/b) \;+\; f(n), \qquad a \geq 1, \;\; b > 1.$

Read this as: “solving a problem of size $n$ costs $a$ recursive solves on subproblems of size $n/b$, plus $f(n)$ non-recursive work to split and combine.” Specific instances:

The Master Theorem reads off $T(n)$ directly from $(a, b, f)$ by comparing $f(n)$ with $n^{\log_b a}$. We'll prove and apply it in Chapter 2; for now the take-away is that decomposition shape determines asymptotic running time, not constants and not implementation tricks.

Worked Example 1: Sum of an Array

Decrease-and-conquer in its purest form. To sum $A[0..n-1]$, recursively sum $A[1..n-1]$ and add $A[0]$. Base case: an empty slice sums to 0.

Call: array_sum([3, 1, 4, 1, 5]) → i defaults to 0

For a = [3, 1, 4, 1, 5] (length 5), this triggers when i = 5

If i = 0 and a = [3, 1, 4, 1, 5], rest = array_sum(a, 1) = 1 + 4 + 1 + 5 = 11

Returns a[0] + rest = 3 + 11 = 14

1def array_sum(a, i=0):
2    # Base case: index past the last element -> empty suffix
3    if i == len(a):
4        return 0
5
6    # Recursive case: A[i] + sum of A[i+1..n-1]
7    rest = array_sum(a, i + 1)
8    return a[i] + rest

The recurrence is $T(n) = T(n-1) + \Theta(1)$, which solves to $T(n) = \Theta(n)$. Stack depth is also $\Theta(n)$ — for $n = 10^6$ on CPython this will hit the recursion limit, a textbook reason to prefer iteration when the decomposition is linear.

Worked Example 2: Maximum Subarray (Three Decompositions)

Given an array $A[0..n-1]$ of integers (possibly negative), find the maximum sum achievable by any contiguous subarray. Example: for $A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]$ the answer is 6, attained by the subarray $[4, -1, 2, 1]$. This problem is famous because it admits three textbook decompositions of strikingly different cost, making it ideal for studying how decomposition shape drives running time.

Decomposition A: Brute Force — $\Theta(n^3)$

Enumerate every pair $(i, j)$ with $0 \leq i \leq j < n$, sum $A[i..j]$ from scratch, take the max. Three nested loops: $\binom{n}{2}$ pairs and a sum of length up to $n$ for each.

1def max_subarray_brute(a):
2    n = len(a)
3    best = a[0]
4    for i in range(n):
5        for j in range(i, n):
6            s = sum(a[i:j+1])     # O(j - i + 1) work
7            if s > best:
8                best = s
9    return best

Decomposition B: Divide and Conquer — $\Theta(n \log n)$

Split $A$ at the midpoint $m$. The optimal subarray either (i) lies entirely in the left half, (ii) lies entirely in the right half, or (iii) crosses $m$. Cases (i) and (ii) are recursive calls; case (iii) is the only one we have to handle directly — sweep outward from $m$ in both directions tracking the best suffix sum to the left and best prefix sum to the right.

1def max_subarray_dc(a, lo, hi):
2    if lo == hi:                           # base case: single element
3        return a[lo]
4    m = (lo + hi) // 2
5
6    # case (i) and (ii): entirely on one side
7    best_left  = max_subarray_dc(a, lo, m)
8    best_right = max_subarray_dc(a, m + 1, hi)
9
10    # case (iii): crosses m — best suffix of A[lo..m] + best prefix of A[m+1..hi]
11    s = 0; left_max = float("-inf")
12    for k in range(m, lo - 1, -1):
13        s += a[k]
14        left_max = max(left_max, s)
15    s = 0; right_max = float("-inf")
16    for k in range(m + 1, hi + 1):
17        s += a[k]
18        right_max = max(right_max, s)
19
20    return max(best_left, best_right, left_max + right_max)

The cross-case sweep is $\Theta(n)$, giving the recurrence $T(n) = 2T(n/2) + \Theta(n)$ → $\Theta(n \log n)$.

Decomposition C: Kadane (DP) — $\Theta(n)$

Define $B[i]$ as the maximum sum of a contiguous subarray ending exactly at index $i$. Then either that subarray is the single element $A[i]$ alone, or it extends the best subarray ending at $i-1$:

$\quad B[i] \;=\; \max\bigl(\,A[i],\ \ A[i] + B[i-1]\,\bigr).$

The answer is $\max_i B[i]$. Because each $B[i]$ depends only on $B[i-1]$ we keep one rolling scalar. This is Kadane's algorithm, and it's the textbook example of how transforming a brute-force search into a DP with overlapping-subproblems structure collapses $\Theta(n^3)$ down to $\Theta(n)$.

Kadane in Two Languages

First, pure Python from scratch — no libraries, no tricks — so the algorithm is naked.

kadane([-2, 1, -3, 4, -1, 2, 1, -5, 4]) → 6

For a = [-2, 1, -3, 4, ...], cur_end starts at -2

For a = [-2, 1, -3, 4, ...], best starts at -2

i=1, a[1]=1, cur_end was -2 → max(1, -2+1) = max(1, -1) = 1. cur_end becomes 1.

i=3, a[3]=4, cur_end was -3 → cur_end = max(4, -3+4) = 4. best = max(1, 4) = 4.

Returns 6 for the input [-2, 1, -3, 4, -1, 2, 1, -5, 4]

1def kadane(a):
2    # B[i] = max subarray sum ENDING at index i (rolling scalar)
3    cur_end = a[0]
4    best    = a[0]
5
6    for i in range(1, len(a)):
7        # Extend the previous best-ending-here, OR restart at A[i] alone
8        cur_end = max(a[i], cur_end + a[i])
9        # Track the global best across all i
10        best    = max(best, cur_end)
11
12    return best

Now a vectorized PyTorch version — useful when you have a batch of sequences (e.g., per-instrument returns in a finance pipeline, or per-channel anomaly scores in time-series models) and want to fuse the sweep into a single GPU kernel via $\text{cummax}$ on prefix sums.

Input shape (4, 1000) → output shape (4,)

a = [3, -2, 5] → prefix = [3, 1, 6]

a = [3, -2, 5] → prefix = [0, 3, 1, 6]

prefix = [0, 3, 1, 6] → run_min = [0, 0, 0, 0]

prefix[1..]=[3,1,6], run_min[..-1]=[0,0,0,0] sliced to [0,0,0] → diffs = [3, 1, 6]

diffs = [3, 1, 6] → returns tensor(6)

1import torch
2
3def kadane_torch(a: torch.Tensor) -> torch.Tensor:
4    # a: (B, n) batch of sequences. Returns (B,) of max subarray sums.
5    # Identity: max_{i<=j} sum(A[i..j]) = max_j ( prefix[j] - min_{i<=j} prefix[i-1] )
6    prefix = torch.cumsum(a, dim=-1)                          # (B, n)
7    zero   = torch.zeros_like(prefix[..., :1])
8    prefix = torch.cat([zero, prefix], dim=-1)                # (B, n+1)
9
10    # Running min of prefix[0..j], i.e., smallest "starting" prefix
11    run_min = torch.cummin(prefix, dim=-1).values             # (B, n+1)
12
13    # max over j of ( prefix[j+1] - run_min[j] )
14    diffs = prefix[..., 1:] - run_min[..., :-1]               # (B, n)
15    return diffs.max(dim=-1).values                           # (B,)

Both implementations compute the same answer, but the second one leverages a transform-and-conquer insight: rewriting the problem in terms of prefix sums turns it into a difference query over running minima, which fuses cleanly onto vector hardware. Same problem — better representation.

Interactive: Decomposing Merge Sort

Decomposition trees are easier to feel than to describe. The widget below walks merge sort through both phases on an 8-element array. Press Step to either split a node or merge a pair.

Things to notice as you step through:

• The split phase is a pre-order walk — we always handle a parent before its children.
• The merge phase is the mirror image: a post-order walk — a parent can only merge after both its children have already merged. This is induction in motion.
• The tree has exactly $\log_2 8 = 3$ levels (excluding the leaves) and $8$ leaves — matching the asymptotics for $n = 8$.
• Each level processes $\Theta(n)$ elements in total during merge, and there are $\Theta(\log n)$ levels → the famous $\Theta(n \log n)$.

Decomposition in Real Systems

The five strategies aren't academic exercises — they are the skeletons of the systems you use every minute.

Notice how often transform-and-conquer is the hidden engine: red-black trees in the Linux kernel, prefix sums on GPUs, de Bruijn graphs in bioinformatics. The work is in choosing a representation in which the problem you care about is trivial.

Recognizing Which Strategy Fits

Given a fresh problem, run this checklist. The first “yes” usually wins.

1. Can I split the input into ~$a$ independent pieces of size $n/b$? If the pieces don't need to talk to each other, you have divide and conquer. (Sorting halves, FFT halves, BVH octants.)
2. Can I solve a slightly smaller instance and finish in $O(1)$ or $O(n)$? Then it's decrease and conquer. (Insertion sort, GCD, binary search.)
3. Is there a representation in which my problem is easy? Transform and conquer. Sorting first, building a hash table, mapping to a graph, switching from time domain to frequency domain.
4. Do my recursive subproblems repeat? Then memoize and you have dynamic programming. The diagnostic: draw two levels of the recursion tree and look for nodes labeled with the same subproblem.
5. Is the candidate space small (or am I just sanity-checking my fast algorithm)? Brute force is fine and is often the right baseline.
6. Is the input itself a tree, graph, or recursively-defined object? Then the natural decomposition follows the structure of the input. (Tree algorithms, JSON/AST traversals, file-system walks.)

Correctness and Efficiency Intuition

Correctness via structural induction

A recursive algorithm is correct iff: (1) it returns the right answer on every base case, and (2) assuming the recursive calls return the right answer on their (strictly smaller) inputs, the combine step produces the right answer on the current input. This is the induction hypothesis in computational form. For kadane the base case is the singleton subarray $A[0]$ with answer $A[0]$; the inductive step is the recurrence $B[i] = \max(A[i],\ A[i] + B[i-1])$ — if we believe $B[i-1]$ is correct, the case analysis (start fresh vs. extend) is exhaustive, so $B[i]$ is correct.

Efficiency = depth × work-per-level

Once you have a decomposition tree, asymptotic cost falls out by accounting:

1. Depth — how many levels deep does the tree go? Halving gives $O(\log n)$; decreasing by 1 gives $O(n)$.
2. Branching — how many children per node? Constant $a$ children with shrinkage factor $b$ means level $k$ has $a^k$ nodes of size $n/b^k$.
3. Per-node work — the non-recursive cost of decompose + combine at a node of size $m$.
4. Sum it up: total work = $\sum_{\text{nodes}} f(\text{size of node})$. For balanced trees this collapses to a clean closed form via the Master Theorem.

Two algorithms with the same big-O often differ in which term dominates — e.g., merge sort vs. heapsort are both $\Theta(n \log n)$, but heapsort's constant is larger because heap operations have worse cache locality. The shape of the decomposition predicts not just asymptotic order but also memory access patterns, parallelism, and even numerical stability (Strassen is famously less numerically stable than the naive algorithm despite being asymptotically faster).