Recurrence Relation

Introduction:-

A recurrence relation is a mathematical expression that defines a sequence in terms of its previous

terms.

Each number in the sequence depends on the ones that came before it, following a certain pattern

or rule.

A recurrence relation is a way to express this pattern or rule mathematically.

General form of a Recurrence Relation: an=f(an−1,an−2,...,an−k)

where f is a function that defines the relationship between the current term and the previous terms.

an represents the nth term in the sequence.

Example:

We can use recurrence relation to generate a sequence. Each term is generated by previous term. In

this we are adding +4 to the previous term to get next term of sequence. So recurrence relation can

be given as: Un+1=Un+4

26101418

Significance of Recurrence Relations in DSA:-

Recurrence Relations play a significant role in analyzing and optimizing the complexity of

algorithms. Recurrence relations are used to analyze the running time of recursive function.

Some of the common uses of Recurrence Relations are:

 Time Complexity Analysis

 Analysing Recursive Algorithms

 Divide and Conquer Algorithms

.

Common Examples of Recurrence Relations:-

Example Recurrence Relation

Fibonacci Sequence F(n) = F(n-1) + F(n-2)

Factorial of a Number n F(n) = n * F(n-1)

Merge Sort T(n) = 2*T(n/2) + O(n)

The running time of a recursive function is denoted by T(n)) where n is the size of the input. In

recurrence relation, the running time of a recursive function of input size n is expressed in terms of

the running time of the lower value of n.

For example

T(n)=T(n−1)+O(1)

Here, the running time for size n is equal to the running time for size n−1 plus a constant time.

Usually, the running time T(n) is expressed as a conditional statement having the following two

conditions

1. Base Case: The base case is the running time of an algorithm when the value of n is small

such that the problem can be solved trivially.

2. Recursive case: The recursive running time is given by a recurrence relation for a large value

of n.

Types of Recurrence Relations:-

Various types of Recurrence Relations are:

1. Linear Recurrence Relations

1. Divide and Conquer Recurrences

1. Substitution Recurrences

1. Homogeneous Recurrences

1. Non-Homogeneous Recurrences

How to Solve Recurrence Relations:-

To solve a Recurrence Relation means to obtain a function defined on the natural numbers that

satisfy the recurrence.

There are four methods for solving Recurrence:

1. Substitution Method

2. Recursion Tree Method

3. Master Method

Here are the general steps to analyze the complexity of a recurrence relation:

 Substitute the input size into the recurrence relation to obtain a sequence of terms.

 Identify a pattern in the sequence of terms, if any, and simplify the recurrence relation

to obtain a closed-form expression for the number of operations performed by the

algorithm.

 Determine the order of growth of the closed-form expression by using techniques such

as the Master Theorem, or by finding the dominant term and ignoring lower-order

terms.

 Use the order of growth to determine the asymptotic upper bound on the running time

of the algorithm, which can be expressed in terms of big O notation.

1. Substitution Method:-

We make a guess for the solution and then we use mathematical induction to prove the guess is

correct or incorrect

We need to prove that T(n) <= cnLogn. We can assume that it is true for values smaller than n.

T(n) = 2T(n/2) + n

     <= 2cn/2Log(n/2) + n

       =  cnLogn – cnLog2 + n

       =  cnLogn – cn + n

    <= cnLogn

2. Recursion Tree Method:-

Level of the tree. Finally, we sum the work done at all levels. To draw the recurrence tree, we start

from the given recurrence and keep drawing till we find a pattern among levels. The pattern is

typically arithmetic or geometric series. 

Consider the recurrence relation, T(n) = T(n/4) + T(n/2) + cn2

In this method, we draw a recurrence tree and calculate the time taken by every

            cn2            /      \

  T(n/4)     T(n/2)

If we further break down the expression T(n/4) and T(n/2), we get the following recursion tree.

                    cn2

              /          \      

    c(n2)/16          c(n2)/4

   /         \            /         \

T(n/16)  T(n/8)  T(n/8)    T(n/4) 

Breaking down further gives us following

                        cn2 

                /               \     

       c(n2)/16               c(n2)/4

    /          \               /          \

c(n2)/256  c(n2)/64 c(n2)/64   c(n2)/16

 /    \            /    \       /    \        /    \  

To know the value of T(n), we need to calculate the sum of tree nodes level by level. If we sum

the above tree level by level, we get the following series T(n) = c(n^2 + 5(n^2)/16 + 25(n^2)/256)

+ ….

The above series is a geometrical progression with a ratio of 5/16.

To get an upper bound, we can sum the infinite series. We get the sum as (n2)/(1 – 5/16) which is

O(n2).

3.Master Methods:-

Master Method is a direct way to get the solution. The master method works only for the following

type of recurrences or for recurrences that can be transformed into the following type. 

 

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

There are the following three cases: 

 If f(n) = O(nc) where c < Logba then T(n) = Θ(nLogba) 

 If f(n) = Θ(nc) where c = Logba then T(n) = Θ(ncLog n) 

 If f(n) = Ω(nc) where c > Logba then T(n) = Θ(f(n)) 



Conclusion:-

In conclusion, recurrence relations are fundamental in the analysis and optimization of

algorithms. They provide a mathematical framework for understanding how the

performance of algorithms scales with input size. By expressing algorithms' running time

or space usage in terms of previous values, recurrence relations offer insights into the

efficiency and behavior of various algorithmic strategies.

Name:-Pranav Shankarrao Narwade

Roll No.:-12