Sign in to save

Bookmark this page so you can find it later.

Sign in to save

Bookmark this page so you can find it later.

Recurrence Relations & Master Theorem cheat sheet - grade college

Click image to open full size

Math Grade college

Recurrence Relations & Master Theorem Cheat Sheet

A printable reference covering characteristic equations, repeated roots, nonhomogeneous recurrences, recursion trees, and the Master Theorem for college.

TopicsAlgorithmsAlgebraFunctionsCountingComputer Science
Download PNG

Related Tools

Related Labs

Related Worksheets

Related Infographics

Study as Flashcards

Recurrence relations describe sequences where each term depends on earlier terms, and they are central in discrete math, algorithms, and computer science. This cheat sheet helps students recognize common recurrence types and solve them efficiently. It is especially useful for analyzing recursive algorithms and proving growth rates.

The focus is on linear recurrences, characteristic equations, and divide-and-conquer running times.

For linear homogeneous recurrences, the main idea is to turn the recurrence into a characteristic equation and use its roots to build the general solution. Repeated roots add extra powers of nn, while nonhomogeneous terms require a particular solution. For algorithm analysis, the Master Theorem solves many recurrences of the form T(n)=aT(nb)+f(n)T(n)=aT\left(\frac{n}{b}\right)+f(n).

Comparing f(n)f(n) with nlog⁡ban^{\log_b a} determines the asymptotic growth.

Key Facts

  • A linear homogeneous recurrence with constant coefficients has the form an=c1an−1+c2an−2+⋯+ckan−ka_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}.
  • The characteristic equation for an=c1an−1+⋯+ckan−ka_n=c_1a_{n-1}+\cdots+c_ka_{n-k} is rk−c1rk−1−⋯−ck=0r^k-c_1r^{k-1}-\cdots-c_k=0.
  • If the characteristic equation has distinct roots r1,r2,…,rkr_1,r_2,\ldots,r_k, then an=A1r1n+A2r2n+⋯+Akrkna_n=A_1r_1^n+A_2r_2^n+\cdots+A_kr_k^n.
  • If a root rr has multiplicity mm, its contribution is (A0+A1n+⋯+Am−1nm−1)rn(A_0+A_1n+\cdots+A_{m-1}n^{m-1})r^n.
  • A nonhomogeneous recurrence an=c1an−1+⋯+ckan−k+g(n)a_n=c_1a_{n-1}+\cdots+c_ka_{n-k}+g(n) has solution an=an(h)+an(p)a_n=a_n^{(h)}+a_n^{(p)}.
  • The Master Theorem applies to recurrences of the form T(n)=aT(nb)+f(n)T(n)=aT\left(\frac{n}{b}\right)+f(n), where a≥1a\geq1 and b>1b>1.
  • In the Master Theorem, the critical comparison function is nlog⁡ban^{\log_b a}.
  • If f(n)=Θ(nlog⁡balog⁡kn)f(n)=\Theta\left(n^{\log_b a}\log^k n\right) with k≥0k\geq0, then T(n)=Θ(nlog⁡balog⁡k+1n)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 a0a_0 and a1a_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)g(n).
Particular Solution
One specific solution to a nonhomogeneous recurrence that accounts for the added term g(n)g(n).
Master Theorem
A theorem that gives asymptotic bounds for many divide-and-conquer recurrences of the form T(n)=aT(nb)+f(n)T(n)=aT\left(\frac{n}{b}\right)+f(n).

Common Mistakes to Avoid

  • Forgetting the initial conditions makes the solution incomplete, because constants such as A1A_1 and A2A_2 cannot be determined without them.
  • Using rnr^n for a repeated root only once is wrong, because a root of multiplicity mm requires rn,nrn,…,nm−1rnr^n,nr^n,\ldots,n^{m-1}r^n terms.
  • Writing the characteristic equation with the wrong signs changes the roots, so an=3an−1−2an−2a_n=3a_{n-1}-2a_{n-2} should give r2−3r+2=0r^2-3r+2=0.
  • Applying the Master Theorem to a recurrence not in the form T(n)=aT(nb)+f(n)T(n)=aT\left(\frac{n}{b}\right)+f(n) is invalid unless it is first transformed into that form.
  • Comparing f(n)f(n) to aa or bb instead of nlog⁡ban^{\log_b a} gives the wrong Master Theorem case, because the critical growth rate is the total work across recursion levels.

Practice Questions

  1. 1 Solve the recurrence an=5an−1−6an−2a_n=5a_{n-1}-6a_{n-2} with a0=2a_0=2 and a1=5a_1=5.
  2. 2 Find the general solution of an=6an−1−9an−2a_n=6a_{n-1}-9a_{n-2}.
  3. 3 Use the Master Theorem to find an asymptotic bound for T(n)=3T(n2)+nT(n)=3T\left(\frac{n}{2}\right)+n.
  4. 4 Explain why the comparison between f(n)f(n) and nlog⁡ban^{\log_b a} represents the balance between work done at the root and work done across recursive subproblems.

Understanding Recurrence Relations & Master Theorem

Initial conditions are not a small detail. They choose one specific sequence from all the sequences that fit the same recurrence rule. A second order recurrence needs two starting values, while an order three recurrence needs three.

After finding the general form, substitute those starting values to determine the unknown constants. Students often make correct algebraic steps but stop too early, leaving constants undetermined.

It is useful to check the first few terms by direct calculation. This catches sign errors and confirms that the formula matches the actual sequence.

Nonhomogeneous recurrences have an extra input term, which can represent a regular addition at every step. A useful method is to guess the shape of a particular solution from that input. For a constant input, try a constant.

For a polynomial input, try a polynomial of the same degree. For an exponential input, try a matching exponential. One important exception occurs when the guess duplicates part of the homogeneous solution.

Then multiply the guess by a suitable power of n until it is independent. This is called resonance.

It explains why some solutions gain an extra factor of n. The same idea appears in differential equations, so learning it here builds a connection across mathematics.

A recursion tree makes divide and conquer recurrences easier to see. Each node represents work done by one recursive call. The root is the original problem.

Lower levels contain smaller subproblems, though there may be more of them. Add the work across one level, then compare levels. In merge sort, each level processes a total amount proportional to n, and there are a number of levels proportional to log n.

The total is therefore proportional to n times log n. In binary search, only one subproblem continues at each step, so the work follows one path with proportional to log n levels. Trees are especially helpful when a recurrence does not fit a standard theorem cleanly.

The Master Theorem is fast, but it has limits. It works best when every recursive call has the same reduced size and when the number of calls stays fixed. It may not apply directly when subproblems have unequal sizes, when the reduction changes with n, or when the outside work behaves irregularly.

In those cases, use a recursion tree, substitution proof, or a more general theorem. Pay close attention to what f of n means. It counts work outside the recursive calls, such as splitting an array, merging results, or scanning input.

The comparison term measures the total work created by the branching structure. Understanding those two sources of cost matters more than memorizing cases. Real programs often combine recursive calls with loops, and the loop cost usually belongs in f of n.