Divide and conquer: independent subproblems | DSA

← BlogDATA STRUCTURES / ALGORITHMSPython example pack ↓

Divide and conquer shrinks a problem, solves subproblems and combines results. Merge sort pays in merging; quicksort pays first in partitioning. Binary search follows a single reduced subproblem and is also classified as decrease-and-conquer.

Two-dimensional closest pair divides byx, solves halves, then checks nearby strip points. Resorting byy at every level can cost O(n log²n); maintainingy order through merging gives O(n log n). The bounded-neighbour rule needs a packing argument.

Overlapping subproblems suggest DP. Parallelism is not free: work is total computation, span is the longest dependency chain, and scheduling/memory add overhead. Not every recursive routine is the same design paradigm.

A worked trace

Summing [1,2,3,4] combines independent halves3 and7, though Python slicing adds copying cost.

Cost and assumptions

Index-based recursive sum has Θ(n) work and Θ(log n) stack; ideal parallel span is Θ(log n).

Executable example

Run with Python 3. Assertions check a small example; they do not constitute a general correctness proof. Some advanced examples are explicitly small models or reference oracles, not full production implementations.

Python 3

def range_sum(a, lo, hi):
    if lo == hi: return 0
    if hi-lo == 1: return a[lo]
    mid=(lo+hi)//2
    return range_sum(a,lo,mid)+range_sum(a,mid,hi)
assert range_sum([1,2,3,4],0,4) == 10

TEST YOUR UNDERSTANDING

Your turn

Why does recursive Fibonacci repeat work?

Reveal the reasoning

Subproblems overlap: fib(n−2) appears on multiple branches. Memoisation solves each state once.

Take it further

Write down the input contract and the invariant before changing the example.
Add empty, boundary, duplicate and adversarial cases where they are relevant. Compare with a simple oracle.
Derive the cost under the stated model; measure several input sizes and explain discrepancies.

Primary reading & lecture notes

Original explanations in this course; these references provide proofs and further reading. Source links may cover the broader module.

MIT 6.046J · Design and Analysis ↗Jeff Erickson · Algorithms ↗

Solve the exercise before moving on.

RasimAtaberkŞahin