Recurrences and the Master Theorem

When an algorithm solves a problem by calling smaller copies of itself, its running time obeys an equation that refers to itself: the cost on an input of size $n$ is some local work plus the cost of the recursive calls on smaller inputs. Such an equation is a recurrence. Counting loops, as in the previous lesson, no longer suffices; we need techniques to turn a recurrence into a closed $\Theta$-bound. This lesson develops three, in increasing order of power and precision, and closes with the Akra–Bazzi method for the uneven splits the Master Theorem cannot handle.

From a recursive algorithm to a recurrence

$\text{Divide-and-conquer}$ is the paradigm CLRS, Skiena, and Erickson all use to introduce recurrences. It has three steps: divide the instance into subproblems, conquer them by recursion, and combine their solutions. Merge sort splits the array in half, sorts each half recursively, and merges the two sorted halves.

The $\text{Merge}$ subroutine walks the two sorted halves with two pointers, repeatedly copying the smaller front element into the output. It touches each of the $n$ elements a constant number of times, so it costs $\Theta (n)$.

Now read the cost off the structure. On an array of size $n$:

• Divide is computing the midpoint, $\Theta (1)$.
• Conquer is two recursive calls, each on $n/2$ elements, costing $2T(n/2)$.
• Combine is the merge, $\Theta (n)$.

Adding these (and noting that a one-element array is sorted at no cost) gives the recurrence

We can write this compactly, and as an inequality (since the combine step costs at most linear), as

and the bulk of the work is justifying that implication. This is the equation we must solve. (We freely write $n/2$ rather than $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$; the floors and ceilings change the answer by lower-order amounts that the asymptotics absorb. Skiena and CLRS both justify dropping them.¹) Throughout we also assume a constant base case, which lets us ignore the boundary condition when finding the asymptotic order.

Method 1: the recursion tree

The most intuitive method draws the recurrence. Each node is a subproblem labeled with the non-recursive work it does; its children are the subproblems it spawns. Summing all node labels gives $T(n)$.

For merge sort, the root does $cn$ work and has two children of size $n/2$. Each of those does $c(n/2)$ work and has two children of size $n/4$, and so on, until the leaves are size-$1$ subproblems.

Every level sums to $cn$. The root level is $cn$; the next level is $2\cdot c(n/2)=cn$; the level below is $4\cdot c(n/4)=cn$. The subproblem sizes shrink by half each level, so the tree has ${\log }_{2}n+1$ levels (from size $n$ down to size $1$), and the bottom level holds the $n$ size-$1$ leaves. Therefore

This is the result: merge sort runs in $\Theta (n\log n)$ time, strictly better than insertion sort's $\Theta (n^2)$.² The recursion tree also exposes why: the per-level work stays flat at $cn$ while the depth is only logarithmic.

The tree is a derivation, not yet a proof — it asks us to trust the level sums and the level count. When a recurrence is irregular (unequal splits, work that isn't a clean power of $n$), the tree still gives a reliable guess, which we then certify with the next method.

import math
from dataclasses import dataclass

@dataclass(frozen=True)
class TreeLevel:
  """
    One level of the recursion tree.\n
    `depth` is 0 at the root; `node_count` is a^depth subproblems;\n
    `subproblem_size` is n / b^depth; `work` is the total non-recursive\n
    work summed across that level's nodes.\n
  """

  depth: int
  node_count: int
  subproblem_size: float
  work: float

@dataclass(frozen=True)
class RecursionTree:
  """
    The fully expanded tree for one input size.\n
    `levels` runs root-to-leaves; `total_work` sums their work; `depth` is\n
    the count of internal (non-leaf) levels, i.e. floor(log_b n); and\n
    `leaf_count` is the number of size-1 subproblems at the bottom.\n
  """

  levels: list[TreeLevel]
  total_work: float
  depth: int
  leaf_count: int

def build_recurrence_tree(
  input_size: int,
  subproblems: int,
  shrink_factor: int,
  combine_coefficient: float = 1.0,
  combine_exponent: float = 1.0,
) -> RecursionTree:
  """
    Expand T(n) = a T(n/b) + f(n) for n = `input_size`, with a =\n
    `subproblems`, b = `shrink_factor`, and a polynomial combine cost\n
    f(m) = `combine_coefficient` * m^`combine_exponent`.\n
    The tree descends until subproblems reach size 1, summing the work of\n
    every node so the total equals the recurrence's value at `input_size`.\n
  """
  # reject inputs the recurrence isn't defined for.
  if input_size < 1:
    raise ValueError("input size n must be >= 1")
  if subproblems < 1:
    raise ValueError("number of subproblems a must be >= 1")
  if shrink_factor < 2:
    raise ValueError("shrink factor b must be an integer >= 2")

  # accumulators for the expanded tree.
  levels: list[TreeLevel] = []
  total_work: float = 0.0

  # walk state: root is one node of size n at depth 0.
  current_size: float = float(input_size)
  node_count: int = 1
  depth: int = 0

  # expand internal levels: stop once subproblems have shrunk to size 1.
  while current_size > 1:
    # this level's nodes each pay f(size); sum it across the level.
    work_per_node: float = combine_coefficient * (current_size**combine_exponent)
    level_work: float = node_count * work_per_node

    levels.append(
      TreeLevel(
        depth=depth,
        node_count=node_count,
        subproblem_size=current_size,
        work=level_work,
      )
    )
    total_work += level_work

    # descend: a-fold more nodes, each b times smaller.
    node_count *= subproblems
    current_size /= shrink_factor
    depth += 1

  # the leaf level: size-1 subproblems each costing a constant (taken as 1).
  leaf_count: int = node_count
  leaf_work: float = float(leaf_count)

  levels.append(
    TreeLevel(
      depth=depth,
      node_count=leaf_count,
      subproblem_size=1.0,
      work=leaf_work,
    )
  )
  total_work += leaf_work

  return RecursionTree(
    levels=levels,
    total_work=total_work,
    depth=depth,
    leaf_count=leaf_count,
  )

def per_level_work(tree: RecursionTree) -> list[float]:
  """
    The work at each level, root first — the column the lesson sums.\n
    For merge sort (a = b = 2, f(n) = n) every internal level equals n;\n
    for a root-heavy recurrence it shrinks geometrically from the root.\n
  """
  return [level.work for level in tree.levels]

def tree_depth(input_size: int, shrink_factor: int) -> int:
  """
    The number of times n can be divided by b before reaching 1,\n
    i.e. floor(log_b n) — the count of internal levels in the tree.\n
  """
  if input_size < 1:
    raise ValueError("input size n must be >= 1")
  if shrink_factor < 2:
    raise ValueError("shrink factor b must be an integer >= 2")
  return int(math.floor(math.log(input_size, shrink_factor)))

Method 2: substitution (guess and verify)

The substitution method is the rigorous one: guess the form of the answer, then prove it by induction on $n$. It is the only method that always works, and the only one that produces a complete proof.

We verify the guess $T(n)=O(n\log n)$ for the merge-sort recurrence $T(n)=2T(n/2)+cn$.

A symmetric argument with the inequality reversed gives $T(n)=\Omega (n\log n)$, and together they yield $T(n)=\Theta (n\log n)$, confirming the tree.

Two warnings the standard references repeat:

• Guess the right form. Substitution verifies a guess; it cannot invent one. Use the recursion tree (or the Master Theorem below) to find the candidate.
• Land on the exact bound. The inductive step must end at the same inequality it assumed, with the same constant. Close enough plus a lower-order term is not a proof, as the next example shows.

A failing guess, and why it fails

Watch the method reject a wrong answer. Take the same recurrence, $T(n)=2T(n/2)+n$, and guess $T(n)=O(n)$; concretely, try to prove $T(n)\le cn$ for some constant $c>0$. Substitute the hypothesis $T(n/2)\le c\frac{n}{2}$:

It is tempting to declare victory here: $cn+n=O(n)$, so we are done. That reasoning is circular hand-waving, and CLRS singles it out as the classic substitution error.³ The induction committed to the exact statement $T(n)\le cn$ with one fixed constant $c$ that works for every $n$. The step must therefore arrive at $\le cn$ on the nose, and

which never holds. No choice of $c$, however large, absorbs the leftover $+n$; making $c$ bigger inflates both sides equally. The induction is stuck, and it is stuck for a good reason: the claim is false. We already know $T(n)=\Theta (n\log n)$, which is not $O(n)$. The failed algebra is the method working as designed — a wrong guess leaves a residual that cannot be paid for.

The escape is to strengthen the guess. For this recurrence the honest fix is to raise its order to $T(n)\le dn{\log }_{2}n$, reproducing the proof carried out above: the substitution then produces the residual $-(d-c)n$, which is negative for $d\ge c$ and absorbs the linear term.

Strengthening by subtracting a lower-order term

A subtler failure mode: the guess has the right order and still gets stuck. Consider

The tree says $\Theta (n)$: the per-level work is $1,2,4,\dots$, a geometric series dominated by its last term, the $n$ leaves. So guess $T(n)\le cn$ and substitute:

Off by $+1$ — and no constant $c$ kills a leftover that survives every doubling of $c$, for the same reason as before. Yet the guess's order is correct. The fix, which CLRS presents with this exact recurrence, is counterintuitive: strengthen the claim by subtracting a lower-order term.³ Guess

Substituting the stronger hypothesis on $\lfloor n/2\rfloor$:

whenever $d\ge 1$. Choosing $d=1$ (and $c$ large enough to cover the base case) completes the induction. The stronger hypothesis helps rather than hurts because it is assumed on the subproblems too: each of the two recursive calls brings a $-d$ credit, and the two credits pay for the $+1$ of local work with one $-d$ to spare. Proving less was impossible; proving more is easy.

import math
from dataclasses import dataclass
from typing import Callable

# floating residual comparisons tolerate tiny rounding either side of zero.
_TOLERANCE: float = 1e-9

@dataclass(frozen=True)
class StepFailure:
  """
    A single size where the inductive step failed.\n
    `size` is the n that broke; `recurrence_value` is a guess(n/b) + f(n);\n
    `guess_value` is guess(n); the step needs the former <= the latter.\n
  """

  size: float
  recurrence_value: float
  guess_value: float

@dataclass(frozen=True)
class SubstitutionReport:
  """
    The outcome of checking a guessed bound by substitution.\n
    `holds` is True when the inductive step held at every tested size;\n
    `failures` lists the offending sizes otherwise; `max_residual` is the\n
    largest value of (recurrence_value - guess_value) seen, which is <= 0\n
    exactly when the guess survives.\n
  """

  holds: bool
  failures: list[StepFailure]
  max_residual: float

def verify_substitution(
  guess: Callable[[float], float],
  subproblems: int,
  shrink_factor: float,
  combine: Callable[[float], float],
  sizes: range,
) -> SubstitutionReport:
  """
    Check the inductive step of the substitution method for the guessed\n
    upper bound `guess` against T(n) = a T(n/b) + f(n), where a =\n
    `subproblems`, b = `shrink_factor`, and f = `combine`.\n
    For each n in `sizes` it forms the substituted recurrence value\n
    a * guess(n/b) + f(n) and compares it to guess(n); the guess is\n
    certified when that residual stays <= 0 throughout.\n
  """
  # reject parameters outside the recurrence's domain.
  if subproblems < 1:
    raise ValueError("number of subproblems a must be >= 1")
  if shrink_factor <= 1:
    raise ValueError("shrink factor b must be > 1")

  # track the worst residual and the sizes where the step broke.
  failures: list[StepFailure] = []
  max_residual: float = -math.inf

  for size in sizes:
    # substitute the guess into the recurrence and measure the residual.
    recurrence_value: float = (
      subproblems * guess(size / shrink_factor) + combine(float(size))
    )
    guess_value: float = guess(float(size))
    residual: float = recurrence_value - guess_value
    max_residual = max(max_residual, residual)

    # a positive residual means the step broke at this size.
    if residual > _TOLERANCE:
      failures.append(
        StepFailure(
          size=float(size),
          recurrence_value=recurrence_value,
          guess_value=guess_value,
        )
      )

  return SubstitutionReport(
    holds=not failures,
    failures=failures,
    max_residual=max_residual,
  )

def smallest_constant_for_n_log_n(
  combine_coefficient: float, shrink_factor: float = 2.0
) -> float:
  """
    The least constant d for which the guess T(n) <= d*n*log2(n) survives\n
    the inductive step of the merge-sort recurrence T(n) = 2 T(n/2) + c*n.\n
    The lesson's algebra leaves the residual -(d - c)*n, non-positive\n
    exactly when d >= c, so the smallest working d equals the combine\n
    coefficient c. (Generalized: for b subproblems halving, d >= c / log2 b.)\n
  """
  # reject parameters outside the recurrence's domain.
  if combine_coefficient < 0:
    raise ValueError("combine coefficient c must be >= 0")
  if shrink_factor <= 1:
    raise ValueError("shrink factor b must be > 1")

  # residual -(d - c/log2 b)*n vanishes exactly when d hits this value.
  return combine_coefficient / math.log2(shrink_factor)

A second example: counting inversions

A second divide-and-conquer problem makes the point sharply. Its recurrence has the same shape as merge sort but a different combine cost, and the combine cost is the thing you must get right. An inversion of a list $⟨a_1,\dots ,a_n⟩$ is a pair $(i,j)$ with $i<j$ but $a_i>a_j$; the number of inversions measures how far from sorted the list is (a sorted list has $0$, a reversed list has $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$). The task: given $A[\mathrm{1..}n]$, return $\mathrm{ninv}(A)$.

The brute-force algorithm compares every pair and runs in $\Theta (n^2)$. To beat it, mimic merge sort: split $A$ in half, recursively count inversions inside each half, then count the cross inversions, the pairs with one element in the left half and one in the right. That gives a recurrence of the merge-sort form,

The three kinds of inversion partition cleanly along the split. On $A=⟨2,4,1,3⟩$, the inversions within each half are counted by recursion; the cross pairs, a left element greater than a right element, are what the combine step must tally.

Counting cross inversions naively, with a double loop over the two halves, costs $\Theta (n^2)$, so the recurrence becomes $T(n)\le 2T(n/2)+b{n}^2$. Feed that to the recursion tree: the per-level work is now $b{n}^2,2\cdot b(n/2{)}^2=\frac{1}{2}b{n}^2,\dots$, which shrinks geometrically, so the root dominates and the tree sums to $\Theta (n^2)$. That is no improvement. The split bought us nothing because the combine step is as expensive as the brute force.

The recurrence therefore sets a requirement: the combine step must run in $O(n)$, not $O(n^2)$. If we can count cross inversions in linear time, which one can, by counting them while merging the two sorted halves, the recurrence collapses to $T(n)\le 2T(n/2)+O(n)$, the merge-sort recurrence, and we get $\Theta (n\log n)$. The recurrence both predicts the running time and tells you precisely how fast the combine step has to be for divide-and-conquer to pay off.

Method 3: the Master Theorem

Merge sort's recurrence is one instance of a common pattern. The Master Theorem solves every recurrence of the form

where $a\ge 1$ and $b>1$ are constants and $f(n)$ is the divide-and-combine work. Here $a$ is the number of subproblems, $n/b$ is each subproblem's size, and $f(n)$ is the work done outside the recursion.

The theorem compares $f(n)$ against the watershed function$n^{{\log }_{b}a}$, the total cost of the leaves, which equals the number of leaves $a^{{\log }_{b}n}=n^{{\log }_{b}a}$ times the constant base-case cost. Which of the two dominates determines the answer.

The intuition matches the recursion tree. Compare the work at the root, $f(n)$, to the work at the leaves, $n^{{\log }_{b}a}$. In Case 1 the tree is leaf-heavy and the answer is the leaf count. In Case 3 the root work dwarfs everything below it and the answer is $f(n)$. In Case 2 the work is spread evenly across all $\Theta (\log n)$ levels, as we saw for merge sort, giving the extra $\log n$ factor.

Each panel stacks the per-level work from root (top) to leaves (bottom); the bar width is the work at that level. The case is decided by which end is heavier.

Why the cases hold: three trees

The theorem is a statement about geometric series, and the recursion tree makes the series visible.⁴ Unroll $T(n)=aT(n/b)+f(n)$: level $i$ of the tree holds $a^i$ subproblems of size $n/b^i$, each contributing $f(n/b^i)$ of non-recursive work, so

and the leaf level contributes $\Theta (n^{{\log }_{b}a})$. Summing,

When $f(n)=\Theta (n^d)$ is a polynomial, the level sums take a clean form:

a geometric series with ratio $r=a/b^d$. Everything reduces to whether $r$ is above, at, or below $1$ — equivalently, whether $d$ is below, at, or above ${\log }_{b}a$. Skiena states the theorem in exactly this three-way form.⁵

Case 1, leaves dominate ($r>1$). Take $T(n)=4T(n/2)+cn$: here $a=4$, $b=2$, $d=1$, so $r=4/2^1=2$. Reading the tree level by level:

doubling every level. A growing geometric series is dominated by its last term, so the total is within a constant factor of the bottom:

which matches the leaf level: $4^{{\log }_{2}n}=n^{{\log }_{2}4}=n^2$ leaves at $\Theta (1)$ each. The combine work is irrelevant; the answer is the leaf count, $T(n)=\Theta (n^{{\log }_{b}a})=\Theta (n^2)$.

Case 2, balanced ($r=1$). Merge sort, $T(n)=2T(n/2)+cn$: $a=2$, $b=2$, $d=1$, so $r=2/2^1=1$. This is the first tree we drew. The level sums are

— constant at $cn$ for all ${\log }_{2}n+1$ levels. A flat series is just (number of terms) $\times$ (term), so

Neither end of the tree wins; the $\log n$ factor is the number of levels, each pulling equal weight.

Case 3, root dominates ($r<1$). The naive inversion-counting tree, $T(n)=2T(n/2)+b{n}^2$: $a=2$, $b=2$, $d=2$, so $r=2/2^2=\frac{1}{2}$. The level sums

halve every level. A shrinking geometric series is dominated by its first term and bounded by a constant multiple of it:

so $T(n)=\Theta (f(n))=\Theta (n^2)$. The root alone already costs $b{n}^2$; the entire tree below it costs at most as much again.

The ratio test doubles as a sanity check on concrete instances. For $T(n)=8T(n/2)+n^2$: $r=8/2^2=2>1$, Case 1, answer $\Theta (n^{{\log }_{2}8})=\Theta (n^3)$. For $T(n)=2T(n/2)+n$: $r=2/2=1$, Case 2, $\Theta (n\log n)$. For $T(n)=2T(n/2)+n^2$: $r=2/4=\frac{1}{2}<1$, Case 3, $\Theta (n^2)$.

Regularity and the gaps between the cases

Two fine-print clauses matter in practice.

The regularity condition. Case 3 additionally demands $af(n/b)\le kf(n)$ for some constant $k<1$: the combine work one level down must be a constant factor smaller, which is precisely what makes the level sums a shrinking geometric series. For any polynomial $f$ that satisfies Case 3's growth bound the condition holds automatically — as in Example 4 below, where $af(n/b)=\frac{1}{2}f(n)$. It can fail only for contrived oscillating functions that are periodically tiny one level down; CLRS relegates such $f$ to the exercises.⁴ If regularity fails, the theorem does not apply and you must sum the tree by hand.

The gaps. The three cases do not cover every $f$.⁴ Case 1 needs $f$ polynomially smaller than the watershed (smaller by a factor $n^{ϵ}$), and Case 3 polynomially larger; a merely logarithmic separation falls into the crack between the cases. The standard example:

The watershed is $n^{{\log }_{2}2}=n$, and $f(n)=n\log n$ is bigger than $n$ but not bigger by any $n^{ϵ}$ — for every $ϵ>0$, $\log n=o(n^{ϵ})$. Case 2 fails since $n\log n\ne \Theta (n)$; Case 3 fails since $n\log n\ne \Omega (n^{1+ϵ})$. The basic Master Theorem simply does not apply. The recursion tree still works: level $i$ sums to $2^i\cdot \frac{n}{2^i}\log \frac{n}{2^i}=n(\log n-i)$, so

— the sum $\log n+(\log n-1)+\cdots +1$ is arithmetic, totaling $\Theta ({\log }^{2}n)$. So the answer picks up a squared log, which none of the three cases predicts. (CLRS's chapter notes discuss extended versions that handle $f(n)=n^{{\log }_{b}a}{\log }^{k}n$; for this course, fall back to the tree is the reliable rule.)

Worked examples

Example 1, merge sort. $T(n)=2T(n/2)+\Theta (n)$. Here $a=2$, $b=2$, so $n^{{\log }_{b}a}=n^{{\log }_{2}2}=n^1=n$. And $f(n)=\Theta (n)=\Theta (n^{{\log }_{b}a})$, which is Case 2. Therefore

recovering exactly what the tree and substitution gave.

Example 2, binary search.$T(n)=T(n/2)+\Theta (1)$: one subproblem of half size, constant work to pick the side. Here $a=1$, $b=2$, so $n^{{\log }_{2}1}=n^0=1$. Then $f(n)=\Theta (1)=\Theta (n^{{\log }_{b}a})$, Case 2 again, and

Example 3, leaf-dominated. $T(n)=4T(n/2)+n$. Now $a=4$, $b=2$, so $n^{{\log }_{2}4}=n^2$. The combine work $f(n)=n=O(n^{2-ϵ})$ (take $ϵ=1$) is polynomially smaller than the watershed, which is Case 1, so

The recursion has so many leaves ($n^2$ of them) that they dominate the modest linear work per level.

Example 4, root-dominated. $T(n)=2T(n/2)+n^2$. Here $a=2$, $b=2$, watershed $n^{{\log }_{2}2}=n$. The combine work $f(n)=n^2=\Omega (n^{1+ϵ})$ is polynomially larger, a Case 3 candidate. Check regularity: $af(n/b)=2(n/2{)}^2=\frac{1}{2}{n}^2=\frac{1}{2}f(n)\le kf(n)$ with $k=\frac{1}{2}<1$. Regularity holds, so

The root's quadratic work swamps the tree beneath it.

Unequal splits and Akra–Bazzi

The Master Theorem requires every subproblem to have the same size $n/b$. Divide-and-conquer algorithms do not always split evenly: a partition step can split $n$ elements into a third and two-thirds, giving

No single $b$ fits, so the theorem does not apply. The recursion tree still works. Each node of size $m$ does $cm$ work and splits into children of sizes $m/3$ and $2m/3$ — which together are all of $m$ again. So every level where no branch has bottomed out sums to exactly $cn$; once leaves start dropping out, levels sum to at most $cn$.

The tree's depth is no longer uniform. The leftmost branch divides by $3$ each step and reaches size $1$ at depth ${\log }_{3}n$; the rightmost divides by only $3/2$ and survives until depth ${\log }_{3/2}n$. Both depths are $\Theta (\log n)$ — logarithms to different constant bases differ by a constant factor — so

and substitution certifies the guess in the usual way. Erickson works this recurrence as the standard example of a tree the Master Theorem cannot handle.⁶

For a general tool, the Akra–Bazzi method solves the whole family

with different-sized subproblems and reasonable $f$. Stated without proof: find the unique exponent $p$ with ${\sum }_{i=1}^k{a}_i/b_i^p=1$; then

For $T(n)=T(n/3)+T(2n/3)+n$ the balance equation is ${\left(\frac{1}{3}\right)}^p+{\left(\frac{2}{3}\right)}^p=1$, satisfied by $p=1$ (a third plus two-thirds is one). The integral is ${\int }_1^n\frac{u}{u^2}du=\ln n$, so $T(n)=\Theta (n(1+\ln n))=\Theta (n\log n)$, agreeing with the tree. The method also handles floors, ceilings, and small perturbations of the subproblem sizes, which is why its answer can be trusted for the real $T(\lfloor n/3\rfloor )$-style recurrences that code produces. CLRS's chapter notes present Akra–Bazzi as the standard generalization of the Master Theorem;⁷ at this course's level, the balance-equation-plus-integral recipe is all you need, with the tree as a cross-check.

Choosing a method

The methods are complementary, and Erickson in particular urges fluency with all of them:⁸

• Recursion tree: fastest for building intuition and guessing the answer; shows where the work concentrates, and handles uneven splits.
• Master Theorem: fastest for getting the answer when the recurrence fits the $aT(n/b)+f(n)$ template; no derivation needed, but it has gaps.
• Akra–Bazzi: the heavier tool for unequal subproblem sizes, such as $T(n)=T(n/3)+T(2n/3)+n$; solve the balance equation, evaluate one integral.
• Substitution: the rigorous method that always works and produces a proof; use it to certify a guess, or when the others do not apply.

In practice: sketch the tree to guess, apply the Master Theorem if it fits, and reach for substitution whenever you need a guarantee rather than a hunch.

Recurrences of other shapes

The recurrences here shrink $n$ by a constant factor, the divide-and-conquer signature. Linear recurrences with constant coefficients, like $T(n)=T(n-1)+T(n-2)$ (Fibonacci), instead yield to their characteristic equation, whose roots give the closed form — Fibonacci's dominant root is the golden ratio, so $F_n=\Theta ({\varphi }^n)$.⁹ And the Akra–Bazzi method generalizes to the Akra–Bazzi–Leighton form, which admits lower-order perturbations inside each recursive call, putting the floor/ceiling hand-waving on rigorous footing.¹⁰ For anything that fits none of these, the recursion tree plus a substitution proof never stops applying.

Takeaways

• A recursive algorithm induces a recurrence: $T(n)$ = local work + cost of recursive calls on smaller inputs. Merge sort gives $T(n)=2T(n/2)+\Theta (n)$.
• The recursion tree sums the per-node work; for merge sort every level costs $\Theta (n)$ across $\Theta (\log n)$ levels, giving $\Theta (n\log n)$.
• Substitution guesses the form and proves it by induction; it is the only always-applicable, fully rigorous method. The step must land on the exact bound with the same constant — $\le cn+n$, which is $O(n)$ is not a proof. Strengthen the hypothesis (raise the order, or subtract a lower-order term as in $T(n)\le cn-d$) if a residual blocks the step.
• The combine cost drives the answer. Counting inversions has the merge-sort shape $2T(n/2)+(\text{combine})$, but a naive $\Theta (n^2)$ combine gives $\Theta (n^2)$ overall, for no gain. Only a linear combine recovers $\Theta (n\log n)$.
• The Master Theorem solves $T(n)=aT(n/b)+f(n)$ by comparing $f(n)$ to the watershed $n^{{\log }_{b}a}$: leaves win (Case 1), they tie (Case 2, extra $\log n$), or the root wins (Case 3, needs regularity). Behind each case is a geometric series of level sums $a^{i}f(n/b^i)$; for $f(n)=\Theta (n^d)$ the ratio $a/b^d$ against $1$ decides the case in one division.
• The cases have gaps; when $f$ is only non-polynomially separated from the watershed, as in $T(n)=2T(n/2)+n\log n$ (which sums to $\Theta (n{\log }^{2}n)$), fall back to the tree or substitution.
• Unequal splits like $T(n)=T(n/3)+T(2n/3)+n$ escape the Master Theorem but not the tree: full levels still sum to $cn$ over $\Theta (\log n)$ depth, giving $\Theta (n\log n)$. Akra–Bazzi generalizes: solve $\sum a_i/b_i^p=1$ for $p$, then integrate $f$.