# RECURRENCE RELATION

Recurrence relation is used to describe the running time of a recursive algorithm.

A recursive algorithm can be defined as an algorithm which makes a recursive call to itself with smaller data size. Many problems are solved recursively, especially those problems which are solved through **Divide and Conquer technique**. In this case, the main problem is divided into smaller subproblems which are solved recursively. Quick Sort, Merge Sort, Binary search, Strassen’s multiplication algorithm are formulated as recursive algorithms

## Examples of Recurrence Relations:

- Fibonacci Sequence : F(n)=
*F*(*n*−1)+*F*(*n*−2) - Factorial of a Number n :
*F*(*n*)=*n*×*F*(*n*−1) - Merge Sort: Relation :
*T*(*n*)=2×*T*(*n*/2)+*O*(*n*) - Tower of Hanoi :
*H*(*n*)=2×*H*(*n*−1)+1 - Binary Search :
*T*(*n*)=*T*(*n*/2)+1

## Types of Recurrence Relations

Here are types of recurrence relations explained in simple terms with examples:

**Linear Recurrence Relations:**

- Definition: Each term is a simple combination of the previous terms.
- Example:
*F*(*n*)=*F*(*n*−1)+2, where each term is 2 more than the previous one.

**Homogeneous Recurrence Relations:**

- Definition: Each term depends only on previous terms without any external factors.
- Example: Fibonacci sequence
*F*(*n*)=*F*(*n*−1)+*F*(*n*−2), where each term is the sum of the two preceding terms.

**Non-Homogeneous Recurrence Relations:**

- Definition: Each term depends on previous terms and possibly external factors.
- Example: Towers of Hanoi H(
*n*)=2×*H*(*n*−1)+1, where the number of moves depends on the previous number of moves.

**First-Order Recurrence Relations:**

- Definition: Each term depends only on the immediately preceding term.
- Example:
*F*(*n*)=*F*(*n*−1)+3, where each term is 3 more than the previous one.

**Second-Order Recurrence Relations:**

- Definition: Each term depends on the two immediately preceding terms.
- Example:
*F*(*n*)=*F*(*n*−1)+*F*(*n*−2), like the Fibonacci sequence, where each term is the sum of the two preceding terms.

**Constant Coefficient Recurrence Relations:**

- Definition: The coefficients in the relation are constants.
- Example:
*F*(*n*)=2×*F*(*n*−1)+5, where each term is twice the previous term plus 5.

**Variable Coefficient Recurrence Relations:**

- Definition: The coefficients may vary depending on the value of
*n*. - Example:
*F*(*n*)=*n*×*F*(*n*−1), where each term is multiplied by*n*times the previous term.

**Divide and Conquer Recurrence Relations:**

- Definition: Arises in algorithms that use divide and conquer techniques.
- Example: Merge sort
*T*(*n*)=2×*T*(*n*/2)+*n*, where the time taken to sort*n*elements is twice the time taken to sort*n*/2 elements plus the time taken to merge them.

## Common methods for solving Recurrence Relations

**Substitution Method:**

**Approach**:

In the substitution method, you guess the form of the solution and then prove its correctness using mathematical induction. This method is particularly useful for linear homogeneous recurrence relations.**Steps**:

Guess the form of the solution.

Use mathematical induction to prove the correctness of the guess.

Solve for any unknown constants using initial conditions or boundary conditions.**Example**:

For the Fibonacci sequence,*F*(*n*)=*F*(*n*−1)+*F*(*n*−2), we can guess that the solution is of the form F(*n*)=*c*1⋅*ϕn²*+*c*2⋅*ψn*, where*ϕ*and*ψ*are the roots of the characteristic equation*x²*=*x*+1.

**Recurrence Tree Method:**

**Approach**:

In the recurrence tree method, we visualize the recurrence relation as a tree and sum up the costs or values at each level of the tree. This method is particularly useful for divide and conquer algorithms and non-linear recurrence relations.**Steps**:

Represent the recurrence relation as a tree.

Analyze the cost or value at each level of the tree.

Sum up the costs or values over all levels of the tree.**Example**:

For the recurrence relation*T*(*n*)=2⋅*T*(*n*/2)+*n*representing merge sort, you can draw a tree where each level represents a division of the input size by 2, and then sum up the costs at each level.

**Master Method:**

**Approach**:

The master method provides a framework for solving recurrence relations of the form*T*(*n*)=*aT*(*n*/*b*)+*f*(*n*).

where:**T(n)**represents the time complexity of solving a problem of size n.**a**is a constant factor representing the work done at the current level.**b**is a constant factor representing the problem size reduction (often 2).**f(n)**is a function representing the additional work done at the current level, typically expressed in terms of n (e.g., n^c).