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:

1. Fibonacci Sequence : F(n)=F(n−1)+F(n−2)
2. Factorial of a Number n : F(n)=n×F(n−1)
3. Merge Sort: Relation : T(n)=2×T(n/2)+O(n)
4. Tower of Hanoi : H(n)=2×H(n−1)+1
5. 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)=c1​⋅ϕn²+c2​⋅ψ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).