Recurrence Relations

Recursive algorithms reduce a problem of size $n$ to one or more sub-problems of smaller size, solve those recursively, and then combine the results. Their running time cannot be expressed as a simple closed-form sum — it is defined recursively too, as a recurrence relation. The goal of this lecture is to develop methods for solving such relations and extracting their asymptotic class.

We already encountered this in the Fibonacci case: the running time of the naive recursive algorithm satisfied $T(n) = T(n-1) + T(n-2) + 1$, and the analysis required unrolling the recursion to obtain exponential bounds. Here we build a systematic toolkit.

---

Setup and Conventions

A recurrence relation arising from a recursive algorithm typically looks like:

$T(n) = \begin{cases} \Theta(1) & n = 1 \\ aT(n/b) + f(n) & n > 1 \end{cases}$

Before applying any method, two simplifications are standard and do not affect the asymptotic result:

Replace asymptotic notation with concrete constants. $\Theta(1)$ becomes $d$, $O(n)$ becomes $cn$, and so on. This lets us work with equalities rather than set memberships.

Drop floors and ceilings. $\lfloor n/b \rfloor$ and $\lceil n/b \rceil$ both become $n/b$. This is justified: the asymptotic behavior is unchanged, and the algebra becomes much cleaner.

So the canonical form we work with is:

$T(n) = \begin{cases} 1 & n = 1 \\ aT(n/b) + cn^\beta & n > 1 \end{cases}$

where all constants are positive.

---

The Iteration Method

The iteration method is a direct, mechanical approach: substitute the recurrence into itself repeatedly until a pattern emerges, then evaluate at the base case.

Example 1. Solve $T(n) = T(n/2) + c$ with $T(1) = 1$.

$T(n) = T(n/2) + c$ $= T(n/4) + c + c$ $= T(n/8) + c + c + c$ $\vdots$ $= T(n/2^i) + c \cdot i$

The recursion ends when $n/2^i = 1$, i.e., $i = \log_2 n$. Substituting:

$T(n) = T(1) + c \log_2 n = 1 + c \log_2 n = \Theta(\log n)$

Example 2. Solve $T(n) = T(n/2) + n$ with $T(1) = 1$.

$T(n) = T(n/2) + n$ $= T(n/4) + n/2 + n$ $= T(n/8) + n/4 + n/2 + n$ $\vdots$ $= T(n/2^i) + n \sum_{k=0}^{i-1} \frac{1}{2^k}$

The partial sum is a geometric series: $\sum_{k=0}^{i-1} (1/2)^k = \frac{(1/2)^i - 1}{1/2 - 1} = 2(1 - 1/2^i)$. Recursion ends at $i = \log_2 n$:

$T(n) = T(1) + 2n\left(1 - \frac{1}{n}\right) = 1 + 2n - 2 = 2n - 1 = \Theta(n)$

Example 3. Solve $T(n) = 3T(n/4) + n^2$ with $T(1) = 1$.

$T(n) = 3T(n/4) + n^2$ $= 3^2 T(n/4^2) + 3(n/4)^2 + n^2$ $= 3^3 T(n/4^3) + 3^2(n/4^2)^2 + 3(n/4)^2 + n^2$ $\vdots$ $= 3^i T(n/4^i) + n^2 \sum_{k=0}^{i-1} \left(\frac{3}{16}\right)^k$

Recursion ends when $n/4^i = 1$, i.e., $i = \log_4 n$. The geometric sum converges since $3/16 < 1$:

$\sum_{k=0}^{i-1} \left(\frac{3}{16}\right)^k = \frac{(3/16)^i - 1}{3/16 - 1} = \frac{16}{13}\left(1 - (3/16)^i\right)$

So the total is $3^{\log_4 n} \cdot T(1) + \frac{16}{13}n^2(1 - 3/n^2) = n^{\log_4 3} + \frac{16}{13}n^2 - \frac{48}{13}$. Since $\log_4 3 \approx 0.79 < 2$, the $n^2$ term dominates: $T(n) = \Theta(n^2)$.

---

The Master Theorem

The Master Theorem gives an immediate answer for a large family of divide-and-conquer recurrences without requiring the iteration method's algebra. Its domain of applicability is recurrences of the form:

$T(n) = \begin{cases} d & n = 1 \\ aT(n/b) + f(n) & n > 1 \end{cases}$

with $a \geq 1$, $b > 1$, and $f(n)$ asymptotically positive. This models algorithms that split a problem of size $n$ into $a$ subproblems each of size $n/b$, with $f(n)$ being the work done at the current level (the "combine" cost).

The Theorem

The key quantity is $n^{\log_b a}$. The three cases each correspond to a different relationship between $f(n)$ and this threshold:

Case 1. If $f(n) = O(n^{\log_b a - \epsilon})$ for some $\epsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$.

The recursive work dominates. The combine cost $f(n)$ grows strictly slower than $n^{\log_b a}$.

Case 2. If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log n)$.

The recursive work and the combine cost are evenly matched, so each level of recursion contributes equally and the $\log n$ levels accumulate a $\log n$ factor.

Case 3. If $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some $\epsilon > 0$, and $a \cdot f(n/b) \leq c \cdot f(n)$ for some $c < 1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$.

The combine cost dominates. The additional condition — called the regularity condition — ensures that $f$ behaves consistently across recursion levels and is not growing in a pathological way. For well-behaved functions (polynomials, logarithms) it holds automatically.

Simplified Version

When $f(n) = cn^\beta$ (a pure polynomial combine cost), the theorem reduces to a clean comparison of $\alpha = \log_b a$ and $\beta$:

Condition	Result
$\alpha > \beta$	$T(n) = \Theta(n^\alpha)$ — recursion dominates
$\alpha = \beta$	$T(n) = \Theta(n^\alpha \log n)$ — balanced
$\alpha < \beta$	$T(n) = \Theta(n^\beta)$ — combine dominates

This is the version used in most practical analyses. The three examples from the iteration method can be verified immediately:

• $T(n/2) + c$: $a=1, b=2, \alpha=0, \beta=0$. $\alpha = \beta \Rightarrow \Theta(\log n)$. ✓
• $T(n/2) + n$: $a=1, b=2, \alpha=0, \beta=1$. $\alpha < \beta \Rightarrow \Theta(n)$. ✓
• $3T(n/4) + n^2$: $a=3, b=4, \alpha=\log_4 3 \approx 0.79, \beta=2$. $\alpha < \beta \Rightarrow \Theta(n^2)$. ✓

What the Master Theorem Cannot Handle

The theorem requires the recurrence to have the exact form $aT(n/b) + f(n)$. It does not apply when subproblems have different sizes (e.g., $T(n) = T(n/2) + T(n/3) + n$), when the argument decreases by subtraction rather than division (e.g., $T(n) = T(n-1) + c$), or when $f(n)$ falls in a gap between cases 1 and 2 or 2 and 3 without the required $\epsilon$-polynomial separation. The Fibonacci recurrence $T(n) = T(n-1) + T(n-2) + 1$ falls entirely outside its scope.

Application: Binary Search

The recursive formulation of binary search produces the recurrence:

$T(n) = \begin{cases} 1 & n = 0 \\ T(n/2) + 1 & n > 0 \end{cases}$

The base case $n = 0$ corresponds to an empty search space (the recursion bottoms out when $i > j$). Each call does $O(1)$ work plus one recursive call on a half-sized subarray.

By the Master Theorem: $a = 1, b = 2, \alpha = \log_2 1 = 0, \beta = 0$. Since $\alpha = \beta$:

$T(n) = \Theta(n^0 \log n) = \Theta(\log n)$

This confirms the iterative analysis from the previous lecture.

---

Exact Solution for Fibonacci Recurrence

The bounds from Lecture 1 were $T(n) = \Omega(2^{n/2})$ and $T(n) = O(2^n)$. These are correct but loose. The exact value can be pinned down.

Theorem. Let $T(n)$ be the number of nodes in the recursion tree of Fib2. Then $T(n) = 2F_n - 1$.

The proof is by induction. The conclusion is that $T(n) = \Theta(F_n)$.

Now, from the closed formula: $F_n = \frac{1}{\sqrt{5}}(\varphi^n - \hat{\varphi}^n)$ where $\varphi \approx 1.618$ and $|\hat{\varphi}| < 1$. For large $n$ the $\hat{\varphi}^n$ term vanishes and $F_n \sim \varphi^n / \sqrt{5}$, so $F_n = \Theta(\varphi^n)$.

Therefore:

$T(n) = \Theta(\varphi^n) \approx \Theta(1.618^n)$

This is a tighter result than the earlier bounds of $\Omega(1.41^n)$ and $O(2^n)$. The exact base of the exponential is the golden ratio. The earlier bounds were correct but not tight — the true growth lies strictly between $\sqrt{2}^n$ and $2^n$.

---

Worked Exercises

Exercise A — Computational Complexity

Analyze the cost $T(n)$ of the following algorithm in terms of $n$:

function mystery1(int n) → int:
    x = 0
    while n ≥ 1 do:
        n = n/2
        x = x + 1
        tot = tot + mystery2(x)
    return tot

function mystery2(int n) → int:
    let A[1···n] be a new Array
    for i = 1 ··· n do:
        A[i] = 0
    return A[n]

Step 1: analyze mystery2. The loop executes exactly $n$ times with $O(1)$ work per iteration. Cost: $\Theta(n)$.

Step 2: analyze the while loop in mystery1. The variable $n$ is halved at each iteration; as in binary search, the loop runs $\log_2 n$ times. The variable $x$ counts iterations, so at the $k$-th iteration ($k = 1, 2, \ldots, \log n$), mystery2 is called with input $x = k$.

Step 3: sum the costs.

$T(n) = \sum_{k=1}^{\log n} \Theta(k) = \Theta\!\left(\sum_{k=1}^{\log n} k\right) = \Theta\!\left(\frac{\log n \cdot (\log n + 1)}{2}\right) = \Theta(\log^2 n)$

The point of this exercise is that the argument to mystery2 is not $n$ — it is the loop counter $x$, which grows from 1 to $\log n$. Treating it carelessly as $\Theta(n)$ per call and multiplying by $\log n$ would give the wrong answer.

---

Exercise B — Recurrence Relations

Solve the following recurrence using both methods:

$T(n) = \begin{cases} d & n \leq 1 \\ 2T(n/4) + c & n > 1 \end{cases}$

Master Theorem. Here $a = 2$, $b = 4$, $\alpha = \log_4 2 = 1/2$, $\beta = 0$. Since $\alpha > \beta$:

$T(n) = \Theta(n^\alpha) = \Theta(\sqrt{n})$

Iteration method. Unrolling step by step:

$T(n) = 2T(n/4) + c$ $= 2^2 T(n/4^2) + 2c + c$ $= 2^3 T(n/4^3) + 2^2c + 2c + c$ $\vdots$ $= 2^i T(n/4^i) + c\sum_{k=0}^{i-1} 2^k$

Recursion ends when $n/4^i = 1$, i.e., $i = \log_4 n$. The geometric sum evaluates to $2^i - 1$. Substituting $i = \log_4 n$:

$T(n) = 2^{\log_4 n} \cdot d + c(2^{\log_4 n} - 1) = \sqrt{n}\, d + c(\sqrt{n} - 1) = \Theta(\sqrt{n})$

The two methods agree. It is worth pausing on $2^{\log_4 n} = \sqrt{n}$: in general, $a^{\log_b n} = n^{\log_b a}$, a useful identity that appears repeatedly when evaluating iteration method results at the base case.

---

Summary

Three methods for solving recurrences are available, suited to different situations:

The iteration method works on any recurrence but requires identifying the closed form of a sum at the end — usually a geometric or arithmetic series. It is always applicable but can be algebraically demanding.

The Master Theorem is fast and mechanical when applicable: compute $\alpha = \log_b a$, identify $\beta$ from $f(n) = cn^\beta$, compare, and read off the answer. Its limitation is that it handles only the divide-and-conquer form $aT(n/b) + f(n)$ with a polynomial combine cost.

A fourth method — substitution (guess the form of the solution, then prove it by induction) — is mentioned in the course but not developed in these slides. It is particularly useful when you already have a conjecture from one of the other methods and want to prove it rigorously.

The key quantity in all divide-and-conquer analysis is the comparison between the cost of recursion ($n^{\log_b a}$, which encodes how many subproblems accumulate across the recursion tree) and the cost of the combine step ($f(n)$). Whichever grows faster determines the overall complexity; when they are equal, the $\log n$ levels of recursion each contribute equally and produce the $\Theta(n^{\log_b a} \log n)$ middle case.