independent subproblems

When you split a job among coworkers, the split works cleanly only if nobody needs to peek at anyone else's work to finish their own. If two people are secretly editing the same shared page, you cannot just hand out the pieces and walk away. The same condition decides whether divide and conquer is the right tool: the subproblems you create must be independent, meaning each can be solved on its own, with no information flowing between sibling subproblems during the recursion.

Concretely, independence means two things. First, the subproblems operate on separate (or at least non-interfering) parts of the data, so solving one cannot change what another needs. Second — and this is the subtle part — the recursion does not re-encounter the same subproblem on different branches. In merge sort, the left half and the right half are disjoint slices of the array; sorting one tells you nothing you need about the other, and the two recursive calls never share a subproblem. Contrast the naive recursion for Fibonacci: F(n) calls F(n-1) and F(n-2), but F(n-1) itself calls F(n-2), so the subproblem F(n-2) is solved twice — its branches overlap, so it is NOT independent in the useful sense.

This distinction is the dividing line between two whole design paradigms. Independent subproblems mean each is solved exactly once down its own branch, so a clean recurrence like T(n) = 2 T(n/2) + O(n) holds and divide and conquer is efficient. Overlapping subproblems — where the same smaller problem is reachable many ways — make naive recursion blow up exponentially, and the cure is dynamic programming, which solves each distinct subproblem once and stores the answer. Diagnosing which situation you are in is the first decision when you see a recursive structure.