Chapter 5: Recurrences

Source files used: Convex_hull (Lecture 2 notes, D&C paradigm and recurrences), Vanemdeboas (Lecture 4 notes, square-root recurrences), Matrix Multiplication (Recitation 1, Sections 3.3 and 3.4), MIT6_046JS15_pset1 (Exercise 1-2 as practice); textbook Chapter 4 (chap4, Sections 4.3, 4.4, 4.7 and Problem 4-3) as support. No worked examples are included.

1. Big Picture

A recurrence describes a running time in terms of the running time on smaller inputs. Every divide-and-conquer analysis in the course ends with one.

The Master Theorem guide covered the easy shape $aT(n/b)+f(n)$. This guide covers everything else: setting a recurrence up, unequal splits, square-root arguments, and the general methods.

$$\boxed{\text{Write the recurrence from the algorithm, pick a method, get a }\Theta\text{ bound.}}$$

The textbook’s four methods:

• substitution (guess, then prove by induction),
• recursion tree (sum the cost level by level),
• master method (cookbook for equal splits),
• Akra-Bazzi (general unequal splits, uses calculus).

The lectures add one more tool: change of variables for $T(\sqrt{u})$.

---

2. Core Ideas

2.1 Recursive Case and Base Case

A recurrence has a recursive case (calls itself on smaller inputs) and a base case (does not). In algorithm analysis the base case is

$$T(n)=\Theta(1)\quad\text{for }n<n_0$$

for some constant $n_0$. The textbook’s convention: when no base case is stated, assume this one. The asymptotic answer does not depend on which large enough $n_0$ you pick.

---

2.2 Setting Up a D&C Recurrence

Lecture paradigm: divide a problem of size $n$ into $a$ subproblems of size $n/b$ ($a\ge1$, $b>1$), solve each recursively, combine:

$$T(n)=aT(n/b)+[\text{work for merge}]$$

Count the recursive calls (that is $a$), the size of each call (that is $n/b$), and everything else (that is $f(n)$).

---

2.3 Floors, Ceilings, and Inequalities

Floors and ceilings almost never change the asymptotic answer, so drop them. A recurrence written with $\le$ gives only an $O$ bound; with $\ge$, only an $\Omega$ bound.

---

2.4 Bushiness Matters

The number of children per node in the recursion tree controls the leaf count. The textbook contrast: $2T(n/2)+\Theta(n)$ is $\Theta(n\lg n)$, while $8T(n/2)+\Theta(1)$ is $\Theta(n^3)$, even though the second has a smaller $f(n)$. Eight children give far more leaves.

---

2.5 Recursion Trees Generate Guesses

The textbook’s advice: use a recursion tree to guess, then verify the guess with substitution. You can be a little sloppy while guessing; the substitution proof must be exact. The substitution method itself is covered in the Induction guide.

---

3. Main Governing Equations and Formulas

3.1 Recursion Tree Sum for $aT(n/b)+f(n)$

Depth $i$ has $a^i$ nodes, each costing $f(n/b^i)$. The tree has height $\log_b n$ and $n^{\log_b a}$ leaves.

$$T(n)=\sum_{i=0}^{\log_b n-1}a^i f\!\left(\frac{n}{b^i}\right)+\Theta(n^{\log_b a})$$

Use to see which levels dominate (root, all equal, or leaves).

---

3.2 Geometric Levels: Textbook Example

For $T(n)=3T(n/4)+cn^2$, the cost at depth $i$ is

$$3^i c\left(\frac{n}{4^i}\right)^2=\left(\frac{3}{16}\right)^i cn^2$$

A decreasing geometric series, so the root dominates:

$$T(n)<\frac{1}{1-3/16}cn^2+\Theta(n^{\log_4 3})=\frac{16}{13}cn^2+\Theta(n^{\log_4 3})=O(n^2)$$

Use whenever per-level costs shrink by a constant ratio.

---

3.3 Unequal Splits: Textbook Example

$$T(n)=T(n/3)+T(2n/3)+\Theta(n)$$

Each full level costs at most $cn$. The longest path follows the $2n/3$ branch, so the height is $\Theta(\log_{3/2}n)=\Theta(\lg n)$. The number of leaves is only $\Theta(n)$. Result:

$$T(n)=\Theta(n\lg n)$$

Use when subproblem sizes add up to exactly $n$.

---

3.4 Median-Finding Recurrence

$$T(n)=T(\lceil n/5\rceil)+T(7n/10+6)+\Theta(n)$$

The sizes add up to about $9n/10<n$, so the level costs shrink geometrically and $T(n)=\Theta(n)$. The master theorem does not apply. Prove it by substitution (Medians and Induction guides).

---

3.5 Change of Variables

For arguments like $\sqrt{n}$, set

$$m=\lg n,\qquad S(m)=T(2^m)$$

Then $T(\sqrt{n})=T(2^{m/2})=S(m/2)$, and the recurrence becomes a master recurrence in $m$. Solve for $S(m)$ and substitute back $m=\lg n$.

Lecture 4 examples (van Emde Boas):

$$T(u)=T(\sqrt{u})+O(1)\;\Rightarrow\;S(m)=S(m/2)+O(1)=O(\lg m)\;\Rightarrow\;T(u)=O(\lg\lg u)$$ $$T(u)=2T(\sqrt{u})+O(1)\;\Rightarrow\;S(m)=2S(m/2)+O(1)=O(m)\;\Rightarrow\;T(u)=O(\lg u)$$ $$T(u)=3T(\sqrt{u})+O(1)\;\Rightarrow\;S(m)=O(m^{\lg3})\;\Rightarrow\;T(u)=O(\lg^{1.585}u)$$

Textbook Problem 4-3:

$$T(n)=2T(\sqrt{n})+\Theta(\lg n)=\Theta(\lg n\lg\lg n)$$

Use whenever the argument shrinks by a root instead of a constant factor.

---

3.6 Where $\lg\lg u$ Comes From

The lectures give two views:

• binary search over $\lg u$ items costs $O(\lg\lg u)$,
• $T(\lg u)=T\!\left(\frac{\lg u}{2}\right)+O(1)$, which is the same as $T(u)=T(\sqrt{u})+O(1)$.

Halving the number of bits $\lg u$ each step reaches 1 bit after $\lg\lg u$ steps.

---

3.7 Akra-Bazzi Method (Textbook)

For $T(n)=\sum_{i=1}^{k}a_iT(n/b_i)+f(n)$, find the unique real $p$ with

$$\sum_{i=1}^{k}\frac{a_i}{b_i^{\,p}}=1$$

Then

$$T(n)=\Theta\!\left(n^p\left(1+\int_1^n\frac{f(x)}{x^{p+1}}\,dx\right)\right)$$

Textbook example: $T(n)=T(n/5)+T(7n/10)+n$ gives $p\approx0.84$, and since $0<p<1$ the integral gives $T(n)=\Theta(n)$.

Use for unequal splits when a recursion tree is too messy. You often only need to know whether $p<1$, $p=1$, or $p>1$.

---

3.8 Linear Driving Function, Unequal Splits

For $f(n)=\Theta(n)$ and subproblem fractions $\alpha_i$ (so the calls are $T(\alpha_i n)$):

$$\sum_i\alpha_i<1\Rightarrow\Theta(n),\qquad\sum_i\alpha_i=1\Rightarrow\Theta(n\lg n)$$

This is the Akra-Bazzi result with $p<1$ and $p=1$. Median finding is the first case; $T(n/3)+T(2n/3)+n$ is the second.

---

3.9 Subtract-by-One Recurrences (Textbook)

$$T(n)=T(n-1)+\Theta(1)=\Theta(n)\qquad\text{(recursive linear search)}$$ $$T(n)=T(n-1)+\Theta(n)=\Theta(n^2)\qquad\text{(worst-case randomized select, quicksort)}$$

Unroll the sum; the master theorem does not apply.

---

4. Problem-Solving Workflow

1. Write the recurrence from the algorithm: number of calls, size of each call, non-recursive work (Section 2.2).
2. Drop floors, ceilings, and small additive terms like $+6$ inside $T(\cdot)$ for the guess.
3. Identify the shape:
   • $aT(n/b)+f(n)$ → master theorem,
   • argument $\sqrt{n}$ → change of variables (Section 3.5),
   • unequal fractions → recursion tree or Akra-Bazzi (Sections 3.3, 3.7, 3.8),
   • $T(n-1)$ → unroll (Section 3.9).
4. If no shortcut fits, draw the recursion tree and sum the levels to get a guess (Section 3.1).
5. Prove the guess with substitution, using explicit constants (Induction guide).
6. State the final bound with $\Theta$, or with $O$ / $\Omega$ if only one direction was shown.

Practice: Problem Set 1, Exercise 1-2 (g) to (j). Answers to check are in Section 6.2.

---

5. Decision Rules / Decision Trees

5.1 Which Method?

Equal-size subproblems, $aT(n/b)+f(n)$? → master theorem

Argument is $\sqrt{n}$ or $\sqrt[3]{n}$? → change variables $m=\lg n$, then master theorem

Several different fractions, linear $f(n)$? → sum the fractions: $<1$ gives $\Theta(n)$, $=1$ gives $\Theta(n\lg n)$

Unequal fractions, nonlinear $f(n)$? → Akra-Bazzi or recursion tree

Need a rigorous proof? → substitution with explicit constants

5.2 Reading a Recursion Tree

Level costs decrease geometrically? → root dominates, $\Theta(f(n))$

Level costs about equal? → (cost per level) $\times$ (number of levels)

Level costs increase geometrically? → leaves dominate, $\Theta(\text{number of leaves})$

---

6. Important Tables / Correlations Needed

6.1 Course Recurrences

Algorithm	Recurrence	Solution
Merge sort, convex hull	$2T(n/2)+\Theta(n)$	$\Theta(n\lg n)$
Convex hull, naive merge	$2T(n/2)+\Theta(n^2)$	$\Theta(n^2)$
Block matrix multiply	$8T(n/2)+\Theta(1)$	$\Theta(n^3)$
Strassen	$7T(n/2)+\Theta(n^2)$	$\Theta(n^{\lg 7})$
Median of medians select	$T(\lceil n/5\rceil)+T(7n/10+6)+\Theta(n)$	$\Theta(n)$
vEB, one recursive call	$T(\sqrt{u})+O(1)$	$O(\lg\lg u)$
vEB Insert, two calls	$2T(\sqrt{u})+O(1)$	$O(\lg u)$
vEB Successor, three calls	$3T(\sqrt{u})+O(1)$	$O(\lg^{1.585}u)$
Binary search	$T(n/2)+\Theta(1)$	$\Theta(\lg n)$
Randomized select, worst case	$T(n-1)+\Theta(n)$	$\Theta(n^2)$

6.2 Problem Set 1, Exercise 1-2 (g) to (j): Answer Check

Recurrence	Method	Answer
$4T(\sqrt{n})+\lg^5 n$	$S(m)=4S(m/2)+m^5$, case 3	$\Theta(\lg^5 n)$
$4T(\sqrt{n})+\lg^2 n$	$S(m)=4S(m/2)+m^2$, case 2	$\Theta(\lg^2 n\,\lg\lg n)$
$T(\sqrt{n})+5$	$S(m)=S(m/2)+5$, case 2	$\Theta(\lg\lg n)$
$T(n/2)+2T(n/5)+T(n/10)+4n$	fractions sum to $1$	$\Theta(n\lg n)$

---

7. Key Takeaways

• Unstated base case means $T(n)=\Theta(1)$ for small $n$.
• D&C template: $T(n)=aT(n/b)+[\text{work for merge}]$.
• Floors, ceilings, and $+6$ inside $T(\cdot)$ do not change the answer.
• Recursion tree: depth $i$ costs $a^if(n/b^i)$; leaves cost $\Theta(n^{\log_b a})$.
• Use recursion trees to guess, substitution to prove.
• $\sqrt{n}$ arguments: set $m=\lg n$, $S(m)=T(2^m)$.
• $T(u)=T(\sqrt{u})+O(1)=O(\lg\lg u)$; two calls give $O(\lg u)$; three give $O(\lg^{1.585}u)$.
• Linear $f$ with fractions summing to less than 1 gives $\Theta(n)$; summing to exactly 1 gives $\Theta(n\lg n)$.
• Akra-Bazzi: solve $\sum a_i/b_i^p=1$, then integrate $f(x)/x^{p+1}$.
• $T(n-1)+\Theta(n)=\Theta(n^2)$; the master theorem does not apply.