We've now seen three divide-and-conquer algorithms: maximum subarray, merge sort, and quickselect. All three split a problem, recurse, and combine. But their running times are wildly different — O(n log n), O(n log n), and O(n).

Why? The answer is hiding in the shape of their recursion trees.

Think about merge sort: it splits the array in two, recurses on both halves, and does O(n) work to merge. Quickselect splits the array, recurses on one half, and does O(n) work to partition. Both do O(n) work per call, both halve the problem — but one recurses twice and the other recurses once. That difference changes the tree from bushy to spine-like, and the total work changes dramatically.

Slide between balanced and degenerate splits. Watch the tree reshape — depth directly determines how many levels of O(n) work you pay.

Here are three recursion trees. Each one belongs to a different divide-and-conquer algorithm. Can you read their shapes and figure out which is which?

Three recursion trees, three algorithms you already know. One is bushy and symmetric — every node has two children. One is a tall spine — each node has just one child. One is somewhere in between. Your job: match each tree to the algorithm that produces it. The shape of the tree isn't decoration — it is the complexity. A bushy tree means more total work than a spine-like one, even if the per-node cost is identical.

Every divide-and-conquer recurrence can be described by three numbers:

• a — how many subproblems you create at each level
• b — how much smaller each subproblem is (divide the size by b)
• d — the exponent of the work done outside the recursion (the combine step)

The recurrence looks like: T(n) = a * T(n/b) + O(n^d). That notation packs a lot into one line, so let's unpack it with concrete algorithms you already know. Tap a preset algorithm or slide the parameters to feel what each one controls:

Here's how each algorithm maps to the three parameters:

Merge sort has a=2, b=2, d=1. At each level, you create 2 subproblems (left half and right half), each is half the size of the original (divide by 2), and the merge step touches every element once (O(n^1) work). The tree fans out with branching factor 2 and halves the problem at each level.

Quickselect has a=1, b=2, d=1. You only recurse into one side after partitioning, so a=1. The problem still halves (b=2), and the partition step is still O(n) (d=1). Same per-node cost as merge sort, but only one branch instead of two — that single difference changes the total from O(n log n) to O(n).

Binary search has a=1, b=2, d=0. One subproblem, half the size, but the work at each node is just a single comparison — O(1), which is O(n^0). The tree is a spine (single branch) where each node does constant work, giving O(log n) total.

Karatsuba multiplication has a=3, b=2, d=1. Instead of the naive 4 sub-multiplications, Karatsuba cleverly rearranges the algebra to need only 3. That reduction from a=4 to a=3 drops the complexity from O(n^2) to O(n^1.585) — a subtle parameter change with a dramatic payoff.

The relationship between a, b, and d determines which part of the tree dominates — the leaves, the root, or every level equally. Let's play with these parameters and see how they change the tree shape.

Now you have the three knobs: a (branching factor), b (shrinkage rate), and d (per-node work exponent). Slide them around and watch the recursion tree morph in real time. Pay attention to what happens when a exceeds b^d — the leaves start to dominate. When a equals b^d, every level contributes equally. When a is less, the root dominates. These three regimes are the three cases of the Master Theorem, and you're about to see them emerge from the tree shapes.

You just saw the three shapes emerge from the parameter relationships. Here they are side by side — three trees, three complexities. Tap each case to highlight where the work concentrates:

The tree's shape determines which case applies — but there are only three possible shapes. The work either concentrates at the top, spreads evenly, or piles up at the bottom.

Toggle between cases below to see the work distribution as a stacked bar. Watch the proportions shift — does the bar confirm what the tree shape suggested?

Here is the pattern: when a < b^d, work shrinks at each level — the root dominates (think quickselect). When a = b^d, every level contributes equally — total is O(n^d log n) (think merge sort). When a > b^d, work grows — the leaves dominate.

These three cases are the Master Theorem — but instead of memorizing a formula, you are reading it from the tree. The shape tells you the answer.

But what happens when the recursion does not neatly divide by b?

The Master Theorem assumes each subproblem is exactly n/b in size. But real algorithms aren't always that tidy. What happens when one side gets 90% of the elements and the other gets 10%? The tree becomes lopsided — one branch is deep, the other is shallow. Build a lopsided tree and see whether the imbalance changes the final complexity, or whether the O(n) per-level argument still holds even when the split is uneven.

When the subproblem size subtracts instead of divides — like T(n) = T(n-1) + O(n) — the tree becomes a long chain instead of a balanced tree. You get O(n) levels instead of O(log n), and the total work explodes. Drag the slider to increase n and watch the gap between the two strategies widen:

The Master Theorem only applies when the recursion divides by a constant factor. That's the “divide” in divide-and-conquer — and it's what creates the logarithmic depth that makes these algorithms efficient.

Now for the final connection: every recursive function in code hides a recursion tree inside it. The number of recursive calls determines the branching factor. The argument reduction determines the shrinkage. The non-recursive work determines the per-node cost. Let's see if you can extract the tree from the code.

Every recursive function hides a recursion tree inside it. The number of recursive calls in the function body determines the branching factor a. The argument to each recursive call determines the shrinkage b. The non-recursive work outside the calls determines d. You'll see real code snippets — extract the tree parameters from each one, and predict what the tree looks like before it's revealed. This is the skill that turns any recursive function into an instant complexity read.

function mergeSort(arr: number[]): number[] {

  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);

  const left = mergeSort(arr.slice(0, mid));

  const right = mergeSort(arr.slice(mid));

  return merge(left, right);  // O(n) merge

}

You now have a visual tool for analyzing any divide-and-conquer algorithm: draw the recursion tree, look at the shape, and read off the complexity.

Root-heavy tree? The first call dominates — total is O(n^d). Balanced tree? Every level matters — total is O(n^d log n). Leaf-heavy tree? The bottom matters — total is O(n^(log_b a)).

No memorization required. The shape of the tree is the answer. You'll use this mental model every time you encounter a new recursive algorithm — sketch the tree, check the shape, and you'll know the complexity before you write a single line of analysis.

Next: we'll take divide-and-conquer beyond arrays and into geometry, where the combine step gets surprisingly clever.