T(n)=aT(n/b)+C(n). A split defines subdomains, solve returns a minimal sufficient summary, combine constructs the parent summary, and base-sized domains are solved directly.
Recognition signals
The input has a natural midpoint, spatial partition, or hierarchy.
Subregions can be solved independently with little overlap.
Cross-boundary contributions can be combined efficiently.
Subproblems retain the original shape while shrinking substantially.
Recursive levels enable sorting, counting, geometry, or parallel work.
False friends
Signal
Why it is different
Heavily overlapping subproblems
Repeated states call for memoization or DP; pure recursion repeats exponential work.
A combine step harder than the original
If every level recomputes O(n²) work, splitting has not delivered leverage.
Recursion by itself
Recursion is control flow; divide-and-conquer also needs independent subproblems and a summary contract.
Core invariant
solve(lo,hi) returns a complete summary conforming to its domain contract; combine depends only on child summaries and accounts for every cross-domain contribution exactly once.
State, transition, and processing order
Item
Definition
State
A current half-open domain [lo,hi), its returned summary, and optionally a reusable scratch buffer.
Transition
Return directly at the base case; otherwise split, solve child summaries, then combine them.
Frontier / order
Domains awaiting solution or combination on the recursion stack, normally completed postorder.
Python skeleton
def divide_solve(items):
def solve(lo, hi):
if hi - lo <= 1:
return items[lo:hi]
mid = lo + (hi - lo) // 2
left = solve(lo, mid)
right = solve(mid, hi)
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
return merged + left[i:] + right[j:]
return solve(0, len(items))
Correctness sketch
The base-sized domain is correct by direct construction.
Assume inductively that every child call returns its complete contracted summary.
The combine contract preserves internal answers and adds all cross-boundary information, proving the parent and ultimately the root.
Complexity
Time
Space
Parameters
Determined by T(n)=aT(n/b)+C(n); balanced binary split with linear combine is O(n log n)
Typically O(n) scratch plus O(log n) stack
a is child count, b the shrink factor, and C(n) combine cost.
Edge cases
empty input
single-item base case
half-open bounds and midpoint
odd lengths
recursion depth
double-counted cross-boundary objects
Error patterns
Pattern
Why it fails / fix
Inconsistent interval conventions
Use [lo,hi) and hi-lo<=1 consistently to avoid midpoint gaps or overlap.
Slicing at every level
Copies inflate memory and constants; pass bounds and reuse a buffer when performance matters.
No return-summary contract
The parent cannot combine a child result whose meaning was never specified.
Misusing the Master Theorem
Uneven sizes or irregular costs require a recursion-tree or amortized analysis.
Selection and exclusion rules
Define what solve returns before defining the split.
Verify that combine is cheaper than direct solution.
Switch to memoization when overlap is substantial.
Fix half-open bounds and the base case before coding.