Home › Courses › Data Structures & Big-O (CS 201) › Recurrence Relations & the Master Theorem

Data Structures & Big-O (CS 201) · Module 2 of 9

Recurrence Relations & the Master Theorem

How to write and solve the equations that describe a recursive algorithm's running time.

In this module
  1. Writing Recurrence Relations
  2. The Master Theorem
  3. Recursion Trees
  4. Divide-and-Conquer Algorithm Design
  5. Check yourself

Writing Recurrence Relations

  • A recursive algorithm's runtime can be described by a recurrence relation, expressing T(n) in terms of T of smaller inputs plus the work done outside the recursive calls.
  • For example, a recursive algorithm that makes 2 recursive calls on half the input, plus O(n) extra work, is written as T(n) = 2T(n/2) + O(n).
Worked example

Merge sort divides the array in half, recursively sorts each half, then merges them in O(n) time. Write its recurrence relation.

Solution. T(n) = 2T(n/2) + O(n) — two recursive calls on half-sized inputs, plus linear time to merge.

The Master Theorem

  • For recurrences of the form T(n) = aT(n/b) + O(n^d), the Master Theorem compares d to logb(a) to determine the overall complexity.
  • If d < logb(a), T(n) = O(n^logb(a)); if d = logb(a), T(n) = O(n^d log n); if d > logb(a), T(n) = O(n^d).
Worked example

Use the Master Theorem to find the time complexity of T(n) = 2T(n/2) + O(n).

Solution. Here a=2, b=2, d=1. log_b(a) = log₂(2) = 1, which equals d. This is the middle case, so T(n) = O(n^d log n) = O(n log n).

Recursion Trees

  • A recursion tree visualizes the total work done at each level of recursion, helping to sum up the total work across all levels when the Master Theorem doesn't directly apply or as an intuition check.
Worked example

In the recursion tree for T(n) = 2T(n/2) + O(n), how much work is done at each level, and how many levels are there?

Solution. Each level does O(n) total work (the work per subproblem shrinks by half, but the number of subproblems doubles, canceling out); there are log₂(n) levels, giving a total of O(n log n).

Divide-and-Conquer Algorithm Design

  • Divide-and-conquer algorithms, like merge sort and binary search, split a problem into smaller subproblems, solve them recursively, and combine the results.
  • This paradigm often yields more efficient algorithms than a naive approach by breaking a large problem into independent pieces that are each cheaper to solve.
Worked example

How does binary search exemplify the divide-and-conquer paradigm?

Solution. It divides the search space in half at each step (divide), recursively searches the relevant half (conquer), and doesn't need a combine step since finding the target in one half solves the whole problem.

Check yourself

2 of this module's 5 quiz questions. Pick your answers, then check them in the app, with an explanation for every question.

1. What does a recurrence relation describe?

2. In the Master Theorem, what does it mean if d = log_b(a)?

Check my answers, free