Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 225 · Analyzing Algorithms

Recurrences and the Master Theorem

Solve recursive running times step by step. Learn recurrence relations, recursion trees, unrolling and the three cases of the master theorem, with Python demos.

Loops are easy to count: multiply the bounds and you are done. Recursive functions are trickier, because the cost of a call includes the cost of the calls it makes. To analyze them we write the cost as an equation that refers to itself, called a recurrence relation, and then solve it to get a Big O answer.

This lesson shows how to write a recurrence from code, three ways to solve it (unrolling, the recursion tree, and the master theorem), and how to check your answer by counting calls. If recursion itself is new, read recursion first.

Writing a recurrence

Let T(n) be the number of steps needed for an input of size n. Read the function and write down two things: how many recursive calls it makes and on what sizes, and how much work it does outside those calls.

Python
def countdown(n):
    if n == 0:
        return          # base case: constant work
    print(n)            # constant work
    countdown(n - 1)    # one call on size n - 1

One call on n − 1 plus a constant: T(n) = T(n − 1) + 1, with T(0) = 1. Here are some typical shapes you will meet:

Algorithm idea Recurrence Solution
Walk a list recursively T(n) = T(n−1) + 1 O(n)
Binary search T(n) = T(n/2) + 1 O(log n)
Insert into a sorted prefix, then recurse T(n) = T(n−1) + n O(n²)
Merge sort T(n) = 2T(n/2) + n O(n log n)
Naive Fibonacci T(n) = T(n−1) + T(n−2) + 1 O(φⁿ), about O(1.62ⁿ)
Towers of Hanoi T(n) = 2T(n−1) + 1 O(2ⁿ)
Tree traversal over n nodes T(n) = T(left) + T(right) + 1 O(n)

Method 1: unrolling (substitution)

Expand the recurrence a few times, spot the pattern, and sum it.

TEXT
T(n) = T(n-1) + n
     = T(n-2) + (n-1) + n
     = T(n-3) + (n-2) + (n-1) + n
     ...
     = T(0) + 1 + 2 + ... + n  =  n(n+1)/2   ->  O(n²)

You can make a computer do this unrolling and compare it with the closed form:

Python Evaluating simple recurrences

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The three solved forms are n + 1, n(n+1)/2 and 2ⁿ − 1: linear, quadratic and exponential. The last one is exactly the number of moves in the Towers of Hanoi puzzle (see recursion patterns).

Method 2: the recursion tree

The recursion tree draws every call as a node, labeled with the work that call does outside its recursive calls. Add the work level by level, then add the levels. This is the most visual method and the one that explains the master theorem.

For merge sort, T(n) = 2T(n/2) + n:

TEXT
level 0:                    [ n ]                          work = n
                          /       \
level 1:            [ n/2 ]       [ n/2 ]                  work = 2 * n/2 = n
                    /    \         /    \
level 2:        [n/4]  [n/4]    [n/4]  [n/4]               work = 4 * n/4 = n
                 ...
level log n:   [1] [1] [1] ... [1]                         work = n

total = n per level * (log2 n + 1) levels  ->  O(n log n)
Python A recursion tree, level by level

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each level costs 16 and there are 5 levels (log₂ 16 + 1), so the total is 80 for n = 16. Change the call to tree_levels(16, 3, 2, lambda s: s) and watch the shape change: with three children per node the work per level grows going down, so the bottom level dominates.

The pattern is the entire master theorem in disguise. Per level the work either grows (leaves dominate), stays equal (every level counts, which adds a log n factor), or shrinks (the root dominates).

Method 3: the master theorem

For divide-and-conquer recurrences of the form

TEXT
T(n) = a * T(n / b) + Θ(n^d)        with a >= 1, b > 1, d >= 0

(a subproblems, each of size n/b, plus n^d work to split and combine), compare d with the critical exponent log_b a:

Case Condition Result Intuition
1 d < log_b a Θ(n^(log_b a)) tree grows downward: the leaves dominate
2 d = log_b a Θ(n^d · log n) every level costs the same
3 d > log_b a Θ(n^d) the root dominates

The theorem is an exact statement about this family only. It does not apply to T(n) = T(n−1) + 1 (the size shrinks by subtraction, not division) or to recurrences with unequal splits such as quicksort's worst case. This function applies it for you:

Python A master theorem calculator

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check a few by hand:

  • Binary search: a = 1, b = 2, d = 0. log₂ 1 = 0 = d, so case 2: Θ(n⁰ log n) = Θ(log n).
  • Merge sort: a = b = 2, d = 1. log₂ 2 = 1 = d: case 2, Θ(n log n). See merge sort.
  • Tree traversal: a = 2, b = 2, d = 0; the critical exponent 1 is larger than 0, so case 1: Θ(n), as expected for visiting n nodes.
  • Karatsuba multiplies large numbers with three recursive products instead of four. log₂ 3 ≈ 1.585 > 1, so case 1: Θ(n^1.585), better than the schoolbook Θ(n²).
  • 2T(n/2) + n²: d = 2 beats the critical exponent 1, so the root dominates: Θ(n²). The recursion tree shrinks per level: n², n²/2, n²/4, ... which sums to about 2n².

A quick way to remember the cases: compare how fast the number of subproblems grows (a per level) with how fast the work per subproblem shrinks (b^d per level). If a > b^d, the leaves win. If they are equal, the levels tie. If a < b^d, the root wins.

Checking with real call counts

Don't just trust the algebra; count calls. A recursive function that halves its input should take about log₂ n levels, while one that makes two calls on halves visits about 2n nodes.

Python Counting calls and depth

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

halve makes log₂ n + 1 calls, which fits T(n) = T(n/2) + 1 = Θ(log n). split makes 2n − 1 calls: a full binary tree with n leaves has n − 1 inner nodes, so the total is Θ(n), matching case 1 of the master theorem. The depth is only log₂ n + 1 in both, so the stack space of divide-and-conquer is small even when the time is large (compare space complexity).

When the master theorem does not apply

  • Subtraction instead of division: T(n) = T(n−1) + f(n). Unroll it instead. With f(n) = 1 you get O(n); with f(n) = n you get O(n²); with two calls like 2T(n−1) + 1 you get O(2ⁿ).
  • Uneven splits: quicksort in the worst case is T(n) = T(n−1) + n (O(n²)), but with good pivots it is T(n) = T(n/4) + T(3n/4) + n, which the Akra-Bazzi method or a recursion tree solves as O(n log n).
  • Non-polynomial extra work: for example T(n) = 2T(n/2) + n log n needs an extended form of case 2 and gives Θ(n log² n).
  • Overlapping subproblems: naive Fibonacci's tree has about 1.62ⁿ nodes. Memoization collapses it to O(n) (see memoization vs tabulation).

Common mistakes

  • Forgetting the work outside the calls. In merge sort the + n is the merge step; skipping it gives the wrong answer.
  • Mixing up a and b. a is how many calls you make; b is how much each shrinks the problem.
  • Using the theorem on T(n−1) recurrences. It needs division of the input.
  • Reading the base case into the answer. The base case sets a constant, not the growth rate.
  • Stopping at a bound that is too loose. "Merge sort is O(n²)" is true but useless. Aim for the tight bound.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. Which recurrence describes binary search?

    Binary search makes one recursive call on half of the range and does a constant amount of work (one comparison), so T(n) = T(n/2) + 1, which solves to O(log n).
  2. 2. Apply the master theorem to T(n) = 2T(n/2) + n. What is the result?

    a = 2, b = 2, d = 1, so log_b a = 1 = d. Case 2 applies and multiplies n by log n.
  3. 3. For T(n) = 3T(n/2) + n, which case applies and why?

    log₂ 3 is about 1.585, larger than d = 1, so the leaves dominate and the result is Θ(n^1.585).
  4. 4. What does the recurrence T(n) = 2T(n-1) + 1 solve to?

    Each level doubles the number of calls and there are n levels, so the number of calls is 2ⁿ − 1. The master theorem does not apply here because the size shrinks by subtraction.
  5. 5. In a recursion tree, what do you add to get the total running time?

    Each node represents one call with some non-recursive work. Summing that work per level and then over all levels gives the total.

Summary

  • A recurrence expresses the cost of a recursive function in terms of its smaller calls: number of calls, their sizes, and the extra work.
  • Unrolling expands the recurrence and sums the pattern; recursion trees add the work level by level.
  • Master theorem for T(n) = aT(n/b) + Θ(n^d): compare d with log_b a. Smaller gives Θ(n^(log_b a)), equal gives Θ(n^d log n), larger gives Θ(n^d).
  • Common results: binary search Θ(log n), tree traversal Θ(n), merge sort Θ(n log n), Karatsuba Θ(n^1.585).
  • Subtractive recurrences (T(n−1)) are solved by unrolling: T(n−1)+1 is O(n), T(n−1)+n is O(n²), 2T(n−1)+1 is O(2ⁿ).
  • Count calls and depth in code to confirm your analysis.

Next: Complexity Cheat Sheet