Introduction to Divide and Conquer

Divide and conquer is a strategy for designing algorithms, not an algorithm itself. The idea is that a problem you cannot answer directly often becomes easy once it is small enough, so instead of attacking the whole input at once, you break it into smaller copies of the same problem, solve those, and assemble the results.

Merge sort is the standard illustration. To sort an array, sort its left half, sort its right half, then merge the two sorted halves into one. Notice that the instructions for sorting a half are the same instructions you started with. That self-similarity is what makes the recursion work.

Every divide-and-conquer algorithm is built from the same three moves:

1. Divide: break the problem into smaller instances of the same problem.
   • The subproblems must be the same kind of problem, just smaller. Sorting half an array is still sorting; that is what makes the recursion legal.
2. Conquer: solve the subproblems recursively.
   • Once a piece is small enough to answer outright (one element, an empty range), you stop recursing and return directly. That is the base case.
3. Combine: build the answer to the original from the subproblem answers.
   • This is where the real work usually lives. Merge sort's merge step is the combine; binary search's combine is free, because it throws one half away.

The amount of work each algorithm does varies enormously between the divide step and the combine step, and that balance is what decides its running time. Binary search does almost nothing in either, but throws away half the input. Merge sort divides for free and pays for the merge. Quick sort pays during the divide and combines for free.

Nearly every divide-and-conquer function has this skeleton. If you can fill in the four marked pieces, you have designed the algorithm:

function solve(problem) {
  if (isSmallEnough(problem)) {      // 1. base case
    return solveDirectly(problem);
  }

  const pieces = divide(problem);     // 2. divide

  const answers = pieces.map(solve);  // 3. conquer (recurse)

  return combine(answers);            // 4. combine
}

The recursion is easiest to reason about if you trust it: assume the recursive calls return correct answers for smaller inputs, and only verify that your combine step is right. Trying to trace every level of the call stack in your head is how divide and conquer starts to feel harder than it is.

Because the function calls itself, its cost is defined in terms of itself. That is a recurrence relation, and almost every divide-and-conquer algorithm produces one of the same shape:

• a — how many subproblems each call creates.
  • Merge sort makes two recursive calls, so a = 2.
• b — the factor by which the input shrinks.
  • Halving the array means b = 2.
• f(n) — the work done outside the recursive calls.
  • The dividing plus the combining. For merge sort, the O(n) merge.

Reading a, b and f(n) off the code is mechanical, and once you have them the Master Theorem turns the recurrence straight into a complexity class. That is why the two topics are almost always taught together.

The same shape, with different values of a, b and f(n), produces very different running times:

Karatsuba and Strassen are worth a second look. Both beat the obvious algorithm purely by reducing a: doing three half-size multiplications instead of four, or seven instead of eight. Nothing else changes, and the exponent drops.

Given an array of positive and negative numbers, find the contiguous slice with the largest sum. Checking every slice costs O(n²). Divide and conquer does better by noticing that the best slice must be in exactly one of three places:

1. Entirely inside the left half — solve recursively.
2. Entirely inside the right half — solve recursively.
3. Crossing the midpoint.
   • This case cannot be recursive, but it is easy: extend left from the middle taking the best running sum, extend right the same way, and add the two. That is a single O(n) scan.

Take the largest of the three and you have the answer:

Two recursive calls on half the input, plus a linear crossing scan. The result improves on the O(n²) brute force, and the reasoning is the same reasoning merge sort uses.

When these do not hold, the strategy stops paying. A problem whose subproblems overlap belongs to dynamic programming. A problem where combining costs as much as solving gains nothing from the split.

Decrease and conquer is the one most often confused with divide and conquer. It also shrinks the input, but produces a single subproblem rather than several. By that strict definition binary search is decrease and conquer, though almost every textbook still presents it as the introductory divide-and-conquer example, because the divide step and the analysis are identical.

• It often lowers the complexity class outright.
  • O(n²) sorting becomes O(n log n); O(n) searching becomes O(log n).
• It parallelises naturally.
  • Independent subproblems can run on separate cores with no coordination, which is exactly what makes merge sort a good parallel sort.
• It uses the memory hierarchy well.
  • Subproblems eventually shrink enough to fit in cache, so the deeper levels run faster than their operation count suggests.
• But recursion costs stack space.
  • Depth is usually O(log n), which is fine, but an unbalanced split can reach O(n) and overflow.
• And the constant factors can bite.
  • For small inputs the call overhead outweighs the better complexity, which is why real sort implementations switch to insertion sort below roughly 16 elements.

1. Identify the base case first.
   • The smallest input you can answer without recursing, usually n = 0 or n = 1.
2. Decide how to divide.
   • How many pieces (a), and how much smaller each one is (b).
3. Recurse on the pieces.
   • Trust the recursion to return correct answers for smaller inputs.
4. Write the combine step.
   • Turn the subproblem answers into the answer for the whole input.
5. Write down the recurrence and solve it.
   • T(n) = a·T(n/b) + f(n), where f(n) is the divide plus combine cost. Then apply the Master Theorem.

• Forgetting the base case, or getting its boundary wrong.
  • Every recursive branch must eventually reach a case that returns without recursing. A base case of n == 1 in a function that can be called with an empty range will recurse forever.
• Assuming the split is always free.
  • Slicing an array to pass halves around copies them, which quietly turns an O(1) divide step into O(n). Passing low and high indices instead keeps it free.
• Using divide and conquer on overlapping subproblems.
  • Computing Fibonacci by recursing on n-1 and n-2 re-solves the same values exponentially many times. Overlap is the signal to switch to dynamic programming.
• Expecting recursion alone to make something faster.
  • The speedup comes from discarding work or from combining cheaply, not from recursing. T(n) = 2T(n/2) + O(n²) is still Θ(n²); splitting it gained nothing.
• Ignoring the cost of the call stack.
  • A depth of log n is harmless, but an unbalanced split can reach depth n and overflow the stack. This is why quick sort recurses into the smaller side first.

• Divide and conquer is a design strategy: divide into smaller copies of the same problem, conquer them recursively, combine the answers.
• It requires subproblems that are independent. Overlapping subproblems are dynamic programming's territory.
• Every base case must be reachable, and it should be written before the recursive branch.
• The cost always takes the form T(n) = aT(n/b) + f(n), where f(n) is the divide plus combine work.
• Solve that recurrence with the Master Theorem to get the complexity.
• The speedup comes from discarding work or combining cheaply — never from recursion on its own.