Recurrence Relations: Describing Efficiency and Optimization

Recursion is where a function calls itself during its execution; its paradigm breaks a problem into smaller instances of the same problem. Recursion introduces an inherent trade-off between simplicity and efficiency. While recursive solutions are often more intuitive, understanding their time complexity is essential for making informed design decisions. This post will explore recurrence relations, a technique to analyze the time complexity of recursive algorithms.

Recurrence relations often help model and analyze time series data, such as financial market prices, to identify patterns, trends, and potential predictive factors for making investment decisions.

This post is my best effort. It includes notes I used to study for a challenging class. There might be mistakes in the math! If you spot an error, please let me know. I love writing these posts and want them to be the best possible! :)

🌸👋🏻 Join 10,000+ followers! Let’s take this to your inbox. You’ll receive occasional emails about whatever’s on my mind—offensive security, open source, academics, boats, software freedom, you get the idea.

Recurrence relations

Recurrence relations model and describe sequential processes. They are often denoted as:

$a_n = f(a_{n-1}, a_{n-2}, ..., a_1, a_0 )$

Recurrence relations represent a sequence where each term is defined in terms of its preceding terms. The beauty of recurrence relations lies in their ability to express complex patterns and relationships within a sequence succinctly.

The Fibonacci sequence is a famous example of a recurrence relation. It is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1. The sequence begins:

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …$

The recurrence relation is defined as:

$F(n) = F(n-1) + F(n-2)$

where $(F(0) = 0)$ and $F(1) = 1$ .

So, each term in the Fibonacci sequence is the sum of the two preceding terms. For example:

$F(0) = 0$

$F(1) = 1$

Using F(0) and F(1), $F(2) = F(1) + F(0) = 1 + 0 = 1$

$F(3) = F(2) + F(1) = 1 + 1 = 2$

$F(4) = F(3) + F(2) = 2 + 1 = 3$

And so on. Each term is defined in terms of its two preceding terms in this sequence.

Types of recurrence relations

Linear

A linear combination of previous terms characterizes these recurrence relations. Linear recurrence relations is when each term in the sequence is a linear combination of the previous terms. In other words, the $n$ -th term in the sequence is expressed as a sum of multiples of the previous terms.

The general form of a linear recurrence relation of order* $k$ is:

$a_n = c_1a_{n-1} + c_2a_{n-2} + \ldots + c_ka_{n-k} + g(n)$

Here:

$a_n$ is the $n$ -th term in the sequence.
$c_1, c_2, \ldots, c_k$ are constants (coefficients).
$a_{n-1}, a_{n-2}, \ldots, a_{n-k}$ are the previous terms in the sequence.
$g(n)$ is a function that may involve constants or other terms not dependent on previous terms in the sequence.

* The order of a recurrence relation is the number of previous terms used to express the $n$ -th term in the sequence. The highest subscript in the expression determines the order of the recurrence relation. In the above formula, the highest subscript is $n-1$ , so it is a first-order recurrence relation.

Linear recurrence relations often arise in problems where the value of a term depends linearly on the values of the preceding terms.

Example

$a_n = 2a_{n-1} + 3a_{n-2}$

is a linear recurrence relation because each term $a_n$ is a linear combination of the two preceding terms $a_{n-1}$ and $a_{n-2}$ .

Homogeneous

A homogeneous recurrence relation is where the particular solution is set to zero. In other words, the formula has no additional constant terms or non-homogeneous components.

Homogeneous recurrence relations are particularly useful in finding general solutions to linear recurrence relations, and the solution typically involves finding characteristic roots and using them to form a linear combination of terms.

The general form of a homogeneous linear recurrence relation of order $k$ is:

$a_n = c_1a_{n-1} + c_2a_{n-2} + \ldots + c_ka_{n-k}$

Here:

$a_n$ is the $n$ -th term in the sequence.
$c_1, c_2, \ldots, c_k$ are constants (coefficients).
$a_{n-1}, a_{n-2}, \ldots, a_{n-k}$ are the previous terms in the sequence.

The absence of a non-homogeneous component (no $g(n)$ term) makes it a homogeneous recurrence relation.

Example

$a_n = 2a_{n-1} + 3a_{n-2}$

with initial conditions $a_0 = 1$ and $a_1 = 2$ is homogeneous because there are no additional constant terms (terms independent of $a_n$ ) on the right side of the recurrence relation.

Non-homogeneous

A non-homogeneous recurrence relation describes the terms of a sequence where each term is expressed as a function of previous terms in the sequence, and it also includes a non-zero constant term.

Non-homogeneous recurrence relations are useful for problems where the recurrence sequence is influenced by both its own previous terms and an external, non-constant factor or function.

The general form of a non-homogeneous recurrence relation of order $k$ is given by:

$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k} + f(n)$

Here:

$a_n$ is the $n$ -th term in the sequence.
$c_1, c_2, \ldots, c_k$ are constants.
$f(n)$ is a non-zero function of $n$ , representing the non-homogeneous part of the recurrence relation.

The recurrence relation becomes homogeneous if $f(n) = 0$ . The solution to a non-homogeneous recurrence relation involves finding both the particular solution (related to $f(n)$ ), and the homogeneous solution (related to the complementary homogeneous recurrence relation where $f(n)$ is set to 0 in the original recurrence relation). The general solution is then the sum of these two solutions.

Quick definitions

A particular solution to a non-homogeneous recurrence relation is a specific solution that satisfies the original recurrence relation when the non-homogeneous term ( $f(n)$ ) is substituted into it.
A homogeneous solution satisfies the recurrence relation when the non-homogeneous term ( $f(n)$ ) is set to zero. In other words, it represents the solution to the recurrence relation in the absence of any external influences introduced by the non-homogeneous term.
The general solution to a non-homogeneous recurrence relation combines the particular and homogeneous solutions. In mathematical terms, if $Y_p(n)$ represents the particular solution and $Y_h(n)$ represents the homogeneous solution, then the general solution $Y(n)$ is given by: $Y(n) = Y_p(n) + Y_h(n)$ . This general solution encompasses both the specific behavior introduced by the non-homogeneous term and the solution without that term.

The specific form of the non-homogeneous part refers to the mathematical expression or function that represents the external influences or forces affecting a recurrence relation.

Example

$a_n = 2a_{n-1} + 3a_{n-2} + 5^n$

with initial conditions $a_0 = 1$ and $a_1 = 2$ , is non-homogeneous because there is an additional constant term $(5^n)$ on the right side of the recurrence relation.

Non-homogenous part

In other words, the non-homogeneous part refers to the specific term or function that makes the recurrence relation non-homogeneous. Here is another example. Consider the following non-homogeneous recurrence relation:

$a_n = a_{n-1} + 2^n$

In this case, the term $2^n$ is the non-homogeneous part. It’s the part of the recurrence relation that doesn’t follow the same pattern as the homogeneous solution (which would be of the form $a_n = a_{n-1}$ ).

When using the method of undetermined coefficients, you would guess a particular solution for $a_n$ based on the form of the non-homogeneous part (in this case, $2^n$ ), and then determine the coefficients of that particular solution by substituting it into the recurrence relation and solving for the coefficients.

Homogeneous vs. non-homogeneous

Homogeneous recurrence relations only focus on the terms of a sequence and how they’re combined, without adding any extra constant terms. On the other hand, non-homogeneous recurrence relations include extra constant terms, adding an external influence to the sequence evolution.

The distinction lies in whether external factors or influences, and are present in the mathematical relationship describing the sequence.

First-order

A first-order recurrence relation describes the dependence of a sequence of numbers on their previous terms.

Generally, a recurrence relation for a sequence $\{a_n\}$ is given by an equation expressing $a_n$ in terms of one or more of its preceding terms, typically $a_{n-1}$ .

A first-order recurrence relation is beneficial in modeling and analyzing processes where each term in a sequence depends solely on its immediate predecessor, such as in simple exponential growth or decay scenarios.

The general form of a first-order recurrence relation is:

$a_n = f(a_{n-1})$

where $f$ is some function that defines how the current term ( $a_n$ ) depends on the previous term ( $a_{n-1}$ ). The initial term or condition $a_0$ (or another initial value) is usually given to fully determine the sequence.

For example, consider the Fibonacci sequence defined by the recurrence relation:

$F_n = F_{n-1} + F_{n-2}$

with initial conditions $F_0 = 0$ and $F_1 = 1$ . This relation is a second-order recurrence because it involves two preceding terms. If we express it in terms of only the immediately preceding term, we get a first-order recurrence relation:

$F_n = F_{n-1} + F_{n-2} \implies F_n = F_{n-1} + F_{n-1}$

This form is a first-order recurrence relation because the current term $F_n$ depends only on the immediately preceding term $F_{n-1}$ .

Example

$a_n = 3a_{n-1}$

is first-order because it only involves one preceding term $a_{n-1}$ .

Higher-order

A higher-order recurrence relation is a recursive equation that expresses the terms of a sequence in relation to previous terms, where the dependence on more than one preceding term is involved.

While a first-order recurrence relation involves only one previous term, a higher-order recurrence relation involves two or more previous terms.

Thus, higher-order recurrence relations are particularly useful in modeling and analyzing complex dynamic systems and algorithms where the current state depends on multiple preceding states.

The general form of a higher-order linear recurrence relation of order $k$ is given by:

$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k} + f(n)$

where $a_n$ represents the $n$ -th term of the sequence, $c_1, c_2, \ldots, c_k$ are constants, and $f(n)$ is a function of $n$ that may or may not be present.

Solving higher-order recurrence relations can be more complex than solving first-order ones, and the methods for solving them may involve specialized methods depending on the form of the recurrence relation.

Example

$a_n = 2a_{n-1} + 3a_{n-2} + 4a_{n-3}$

is higher-order because it involves three preceding terms $a_{n-1}$ , $a_{n-2}$ , and $a_{n-3}$ .

First-order vs. higher-order

TLDR: Based on the number of preceding terms involved.

First-order recurrence relations involve only one preceding term in the sequence, where each term depends solely on the immediately preceding term. On the other hand, higher-order recurrence relations involve more than one preceding term in the sequence; here, a combination of multiple preceding terms in the sequence determines each term. The distinction lies in the level of dependency on past terms within the recurrence relation.

Solving recurrence relations

Iterative substitution

A fundamental technique involves substituting the recurrence relation with itself to derive a closed-form expression.

A closed-form expression, also known as an explicit formula or closed-form solution, is a mathematical expression that directly computes the value of a function or sequence for any given input without the need for iteration or recursion. In the context of recurrence relations, a closed-form expression provides a direct formula for computing the sequence’s nth term without relying on previous terms. Closed-form expressions are efficient for calculating sequence values without iterative or recursive processes.

This method is beneficial for simple relations. Iterative substitution is a technique used to solve recurrence relations by iteratively substituting the recurrence equation into itself until a pattern or closed-form solution emerges (video).

Let’s consider a simple example using a Fibonacci sequence. This recurrence relation defines the Fibonacci sequence:

$F(n) = F(n-1) + F(n-2)$

with initial conditions $F(0) = 0$ and $F(1) = 1$ .

Let’s use iterative substitution to find a closed-form solution for $F(n)$ .

1. Base case

$F(0) = 0, \quad F(1) = 1$

2. First iteration

Substitute $F(n-1)$ and $F(n-2)$ into the recurrence relation:

$F(2) = F(1) + F(0)$

Since $F(1) = 1$ and $F(0) = 0$ , we get $F(2) = 1$ .

3. Second iteration

Substitute $F(n-1)$ and $F(n-2)$ again:

$F(3) = F(2) + F(1)$

Substituting the values we found in the first iteration:

$F(3) = 1 + 1 = 2$ .

4. Third iteration

$F(4) = F(3) + F(2)$

Substituting the values from the second iteration:

$F(4) = 2 + 1 = 3$ .

5. Fourth iteration

$F(5) = F(4) + F(3)$

Substituting the values from the third iteration:

$F(5) = 3 + 2 = 5$ .

After several iterations, a pattern emerges: $F(n)$ is the sum of the previous two terms, and the sequence starts with 0 and 1. This leads to the closed-form solution for the Fibonacci sequence:

$F(n) = \frac{{\phi^n - (1 - \phi)^n}}{{\sqrt{5}}}$

where $\phi$ is the golden ratio, approximately 1.61803.

So, we arrived at the closed-form solution for the Fibonacci sequence through iterative substitution.

Tree method

The tree method is commonly used for divide-and-conquer algorithms. It involves constructing a recurrence tree and analyzing its structure to derive a closed-form solution (video).

Consider the following recurrence relation:

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

This recurrence relation represents the time complexity of an algorithm that divides the problem into two subproblems of size $\frac{n}{2}$ each, and the work done at each level is $n$ .

Now, let’s solve this recurrence relation using a recurrence tree.

1. Draw the recurrence tree

Start with the root representing $T(n)$ .
For each level, represent the subproblem size and the work done.
Continue until you reach the base case.

Here is the tree for this example:

            T(n)
          /      \
      T(n/2)   T(n/2)
      /  \       /   \
   T(n/4) T(n/4) T(n/4) T(n/4)
     ...   ...   ...   ...
   T(1)  T(1)  T(1)  T(1)

2. Evaluate the work at each level

At each level, sum the work done.
The work done at each level is the product of the number of nodes at that level and the work per node.

   level 0:  T(n)
   level 1:  2 * (T(n/2) + n/2)
   level 2:  4 * (T(n/4) + n/4)
   ...
   level k:  2^k * (T(1) + 1)

3. Simplify the expression

Sum the geometric series and simplify the expression.

$T(n) = n \log_2 n + n \left(1 + \frac{1}{2} + \frac{1}{4} + \ldots + \frac{1}{2^{\log_2 n}}\right)$

The second term is a geometric series that sums to 2.

$T(n) = n \log_2 n + 2n$

So, the solution to the recurrence relation $T(n) = 2T\left(\frac{n}{2}\right) + n$ is:

$T(n) = n \log_2 n + 2n$ .

Master Theorem

You can also use the Master Theorem to solve recurrence relations, which I wrote about in a separate blog post. If the post leads to an error before July 2024, that is because the post has not been published yet. Stay tuned!

Miscellaneous

Non-homogeneous specific form

Depending on the specific form of the non-homogeneous part, solving non-homogeneous relations may involve techniques like:

Undetermined coefficients
- Involves guessing a particular solution based on the form of the non-homogeneous part and then determining the coefficients by substitution into the recurrence relation.
Generating functions
- Transforms recurrence relations into algebraic equations.
- Particularly useful for linear recurrence relations with constant coefficients.
Method of annihilators
- Involves finding a suitable operator (annihilator) that transforms the non-homogeneous recurrence relation into a homogeneous one, which can then be solved using standard methods.
Matrix methods
- Often useful for systems of linear recurrence relations, where the relations can be represented as matrix equations and solved using linear algebra.
Laplace transforms
- Applying these can sometimes simplify the problem by transforming it into a simpler algebraic equation.

The choice of method depends on the specific characteristics of the relation and the non-homogeneous part.

Homogeneous standard methods

Standard methods for solving homogeneous recurrence relations typically involve finding the characteristic equation, determining the roots of this equation, and then using these roots to form a general solution. Some common techniques include roots of the characteristic equation, repeated roots, characteristic equation method, complex roots, and initial conditions.

Roots of the characteristic equation

The characteristic equation is obtained by substituting $y = x^k$ into the recurrence relation, where $k$ is the order of the recurrence relation (the highest power of $n$ in the relation).

For example, for a linear recurrence relation $a_n = c_1a_{n-1} + c_2a_{n-2} + \ldots + c_ka_{n-k}$ , the characteristic equation would be of the form: $x^k - c_1x^{k-1} - c_2x^{k-2} - \ldots - c_k = 0$ .

Solving this equation yields the roots, which are then used to determine the general solution of the recurrence relation. Different methods are employed to derive the general solution depending on the nature of these roots (real, distinct; real, repeated; complex conjugate).

Repeated roots

If the roots are real and repeated, additional terms involving powers of the index are included in the general solution.

A repeated root occurs when the characteristic equation of a homogeneous linear recurrence relation has a root with a multiplicity greater than one. In other words, if a root $r$ of the characteristic equation occurs more than once, it is considered a repeated root.

For example, consider the characteristic equation: $r^2 - 4r + 4 = 0$ .

This equation can be factored as $(r - 2)^2 = 0$ , indicating that $r = 2$ is a root of multiplicity 2, or a repeated root. In this case, $r = 2$ is repeated twice.

Here, additional terms involving powers of the index are included in the general solution. Specifically, for each repeated root $r$ with multiplicity $m$ , the corresponding terms in the general solution will involve powers of $n$ up to $m - 1$ . This ensures that the general solution accounts for the additional degree of freedom the repeated root introduces.

When a repeated root is present in the characteristic equation, it introduces an additional degree of freedom into the solution space. This means there are multiple ways (or degrees of freedom) in which the repeated root can be combined with other elements to satisfy the recurrence relation.

For instance, if $r$ is a repeated root of multiplicity 2, the general solution would include terms involving both $r^n$ and $n \cdot r^n$ . Similarly, if $r$ is a repeated root of multiplicity 3, the general solution would include terms involving $r^n$ , $n \cdot r^n$ , and $n^2 \cdot r^n$ , and so on.

Others

Characteristic equation method
- Involves rewriting the recurrence relation in terms of its characteristic equation, typically of the form ( $ar^n = br^{n-1} + cr^{n-2} + \ldots$ ), where $(a), (b), (c),$ etc., are constants and ( $r$ ) is the unknown variable.
Real roots
- If the roots are real (aka a real number) and distinct (aka different values), the general solution will be a linear combination of terms involving these roots raised to the power of the recurrence’s index.
Complex roots
- If the roots are complex, the solutions involve complex exponentials, which can be expressed in terms of sine and cosine functions.
Initial conditions
- Finally, any given initial conditions are used to determine the specific coefficients in the general solution, yielding the complete solution to the recurrence relation.

Conclusion on recurrence relations

In conclusion, understanding recurrence relations and their types is crucial for analyzing the time complexity of recursive algorithms. Solving recurrence relations involves techniques such as iterative substitution, the tree method, and the Master Theorem.

While recurrence relations present a powerful tool for expressing complex patterns and relationships within sequences, the trade-off between simplicity and efficiency remains a concern. Mathematical analyses should inform algorithmic designs to predict the time complexity associated with recursive approaches.

If you enjoyed this post on recurrence relations, consider reading Recursion: Algorithmic Paradigms, Complexities, and Pitfalls.

Recurrence Relations: Describing Efficiency and Optimization

Recurrence relations

Types of recurrence relations

Linear

Example

Homogeneous

Example

Non-homogeneous

Quick definitions

Example

Non-homogenous part

Homogeneous vs. non-homogeneous

First-order

Example

Higher-order

Example

First-order vs. higher-order

Solving recurrence relations

Iterative substitution

1. Base case

2. First iteration

3. Second iteration

4. Third iteration

5. Fourth iteration

Tree method

1. Draw the recurrence tree

2. Evaluate the work at each level

3. Simplify the expression

Master Theorem

Miscellaneous

Non-homogeneous specific form

Homogeneous standard methods

Roots of the characteristic equation

Repeated roots

Others

Conclusion on recurrence relations

Discover more from [ret]2read