Recurrence Relations & Master Theorem Cheat Sheet

Key Facts

• A linear homogeneous recurrence with constant coefficients has the form $a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}$.
• The characteristic equation for $a_n=c_1a_{n-1}+\cdots+c_ka_{n-k}$ is $r^k-c_1r^{k-1}-\cdots-c_k=0$.
• If the characteristic equation has distinct roots $r_1,r_2,\ldots,r_k$, then $a_n=A_1r_1^n+A_2r_2^n+\cdots+A_kr_k^n$.
• If a root $r$ has multiplicity $m$, its contribution is $(A_0+A_1n+\cdots+A_{m-1}n^{m-1})r^n$.
• A nonhomogeneous recurrence $a_n=c_1a_{n-1}+\cdots+c_ka_{n-k}+g(n)$ has solution $a_n=a_n^{(h)}+a_n^{(p)}$.
• The Master Theorem applies to recurrences of the form $T(n)=aT\left(\frac{n}{b}\right)+f(n)$, where $a\geq1$ and $b>1$.
• In the Master Theorem, the critical comparison function is $n^{\log_b a}$.
• If $f(n)=\Theta\left(n^{\log_b a}\log^k n\right)$ with $k\geq0$, then $T(n)=\Theta\left(n^{\log_b a}\log^{k+1}n\right)$.

Vocabulary

Recurrence Relation

An equation that defines each term of a sequence using one or more earlier terms.

Initial Conditions

The starting values, such as $a_0$ and $a_1$, needed to determine a unique solution to a recurrence.

Characteristic Equation

A polynomial equation formed from a linear homogeneous recurrence whose roots determine the closed-form solution.

Homogeneous Recurrence

A recurrence in which every term involves the sequence itself and there is no extra forcing term such as $g(n)$.

Particular Solution

One specific solution to a nonhomogeneous recurrence that accounts for the added term $g(n)$.

Master Theorem

A theorem that gives asymptotic bounds for many divide-and-conquer recurrences of the form $T(n)=aT\left(\frac{n}{b}\right)+f(n)$.