Foundations
Recurrence Relations
Difficulty: Advanced
When you stare at merge sort or binary search, the running time is not naturally a simple sum like n^2/2 + n/2. It is something more interesting: the cost of a problem of size n is built out of the cost of smaller problems plus a little...
Recurrence Relations
When you stare at merge sort or binary search, the running time is not naturally a simple sum like n^2/2 + n/2. It is something more interesting: the cost of a problem of size n is built out of the cost of smaller problems plus a little glue. That self-referential structure is captured by a recurrence relation, an equation of the form T(n) = ... written in terms of T on smaller inputs.
This lesson teaches you to spot, write, and classify recurrences directly from recursive code. You will identify the two ingredients every recurrence needs (the recursive case and the base case), then translate familiar algorithms into their T(n) equations: factorial gives T(n) = T(n-1) + 1, binary search gives T(n) = T(n/2) + 1, merge sort gives T(n) = 2 T(n/2) + n, and naive Fibonacci gives T(n) = T(n-1) + T(n-2) + 1. You will also group recurrences into three families (linear, divide-and-conquer, and multi-branch) and recognize the Big-O class each typically produces.
This lesson builds on Big-O Notation (Upper Bound), which gave you the language for expressing complexity, and on Mathematical Sequences, which gave you experience with arithmetic, geometric, and Fibonacci-style sequences, exactly the patterns you will see when a recurrence is expanded.
Writing a recurrence is half the battle; the other half is converting it into a closed-form Big-O. That is the subject of the very next lesson, Solving Recurrence Relations.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Define what a recurrence relation is and identify its two components: the recursive case and the base case.
Derive the recurrence relation from a given recursive function by inspecting the code.
Classify recurrences into three families: linear (decrease-by-constant), divide-and-conquer (decrease-by-factor), and multi-branch.
Write the recurrence for classic algorithms: factorial, Fibonacci, binary search, merge sort, and Tower of Hanoi.
Expand a recurrence by repeated substitution to observe the pattern of total work.
Recognize common recurrence patterns and their corresponding Big-O complexities.
Why This Matters
01
Every recursive algorithm has an implicit recurrence relation -- you cannot determine its true time complexity without identifying and understanding that recurrence.
02
Recurrence relations are the bridge between recursive code and Big-O notation: writing the recurrence is the first step, and the next lesson covers solving it.
03
Interview questions frequently ask you to analyze recursive solutions -- being able to write T(n) = 2T(n/2) + O(n) for merge sort on the spot demonstrates deep algorithmic understanding.
04
Recognizing common recurrence patterns lets you instantly classify algorithms: T(n) = T(n/2) + O(1) means O(log n), T(n) = 2T(n/2) + O(n) means O(n log n), and T(n) = 2T(n-1) means O(2^n).
Key Terms
8 terms you'll encounter in this lesson
Recurrence Relation
An equation that defines T(n) in terms of T on smaller inputs plus non-recursive work. It captures the time complexity of a recursive algorithm, e.g., T(n) = T(n-1) + O(1).
Base Case (of a recurrence)
The value of T(n) for the smallest input sizes where no recursion occurs. Typically T(1) = O(1) or T(0) = O(1). Without a base case, the recurrence has no solution.
Linear Recurrence (Decrease-by-Constant)
A recurrence where the input size decreases by a constant each step, such as T(n) = T(n-1) + c. Common in algorithms like factorial and linear scans with recursion.
Divide-and-Conquer Recurrence
A recurrence of the form T(n) = aT(n/b) + f(n), where the problem is split into 'a' subproblems of size n/b, and f(n) is the work to split and combine. Examples: binary search, merge sort.
Multi-Branch Recurrence
A recurrence where a single call spawns multiple recursive calls on overlapping subproblems, such as T(n) = T(n-1) + T(n-2) for naive Fibonacci. These typically lead to exponential time complexity.
Expansion (Unrolling)
The technique of repeatedly substituting the recurrence into itself to reveal a pattern. For example, T(n) = T(n-1) + 1 becomes T(n) = T(n-2) + 1 + 1 = T(n-3) + 3, revealing T(n) = n after k = n steps.
Branching Factor
The number of recursive calls made at each level of recursion. For T(n) = 2T(n/2) + O(n), the branching factor is 2. Higher branching factors generally lead to faster-growing complexity.
Non-Recursive Work
The f(n) term in a recurrence -- the computation done at each level of recursion outside of the recursive calls. For merge sort, f(n) = O(n) represents the merging step.
Heads Up
Common misconceptions to watch out for
"The recurrence IS the time complexity"
The recurrence is an equation that describes the time complexity, not the answer itself. T(n) = 2T(n/2) + O(n) is the recurrence; O(n log n) is the solution. You must solve the recurrence to get the Big-O bound.
"T(n) = T(n-1) + T(n-2) solves to O(n) because there are about n levels"
The number of levels is indeed about n, but the number of calls doubles at each level. The total number of calls grows exponentially -- approximately O(2^n). The branching factor matters as much as the depth.
"Every recursive function has the same recurrence pattern"
Different recursion structures produce fundamentally different recurrences. A function making one call on n-1 (linear), one call on n/2 (logarithmic depth), or two calls on n-1 (exponential) all have vastly different complexities.
"The base case doesn't matter for the recurrence"
While the base case often does not affect the asymptotic Big-O class, it is essential for the recurrence to be well-defined and solvable. Without T(1) = O(1), the expansion never terminates. In some cases (e.g., different base case values), the solution can differ.