Recurrence Relation:

A recurrence relation is a equation or inequality that express a function in terms of its value on a smaller input.

How to solve these recurrences? any idea?

So, there are three ways to solve the recurrence relations.

1. Substitution Method

2. Recursion Tree Method (Iteration Method)

3. Master Theorem

Substitution Method:

In this method, we solve a recurrence relation mathematically(trying to prove it by induction).

Example 1- Find the time complexity of the below recurrence.

T(n) = n + T(n-1) ; n>1

T(n) = 1         ; n=1

Explanation: 

Using substitution method,

T(n) = n + T(n-1)…..eq1

putting n = n-1 in eq1

T(n-1) = (n-1) + T(n-2)…..eq2

again putting n = n-1 in eq2

T(n-2) = (n-2) + T(n-3)…..eq3

putting eq2 –> eq1

T(n) = n + (n-1) + T(n-2)…..eq4

putting eq3 –> eq4

T(n) = n + (n-1) + (n-2) + T(n-3)

.

.

T(n) = n + (n-1) + (n-2) +…..+ (n-k) + T(n-(k+1))

putting,

n-(k+1) = 1

n-k-1 = 1

k = n-2

T(n) = n + (n-1) + (n-2) +…..+ (n-(n-2)) + T(n-(n-2+1))

T(n) = n + (n-1) + (n-2) +…..+ 2 + 1

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

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

T(n) = O(n2)

Example 2- Find the time complexity of the below recurrence.

T(n) = 2T(n-1) – 1 ; n>0

  T(n) = 1 ; otherwise (n=0)

Explanation:

Using substitution method,

T(n) = 2T(n-1) – 1…..eq1

putting n = n-1 in eq1

T(n-1) = 2T(n-2) – 1…..eq2

again putting n = n-1 in eq2

T(n-2) = 2T(n-3) – 1…..eq3

putting eq2 –> eq1

T(n) = 2[2T(n-2) – 1] – 1

T(n) = 22 T(n-2) – 2 – 1…..eq4

putting eq3 –> eq4

T(n) = 22 [2T(n-3) – 1] – 2 – 1

T(n) = 23 T(n-3) – 22 – 2 – 1

.

.

T(n) = 2k T(n-k) – 2k-1 -……- 22 – 2 – 1

putting,

n-k = 0

n = k or k = n

T(n) = 2n T(n-n) – 2n-1 -……- 22 – 2 – 1

T(n) = 2n * 1 – 2n-1 -……- 22 – 2 – 1

T(n) = 2n – (2n-1 +……+ 22 + 2 + 1) <– (geometric progression or G.P.) 

Since (2n-1 +……+ 22 + 2 + 1) = 2n – 1

T(n) = 2n –(2n – 1)

T(n) = O(1) 

Example 3- Find the time complexity of the below recurrence.

T(n) = T(n-1)*n ; n>1

T(n) = 1       ; n=1

Explanation:

Using substitution method,

T(n) = T(n-1)*n…..eq1

putting n = n-1 in eq1

T(n-1) = T(n-2)*(n-1)…..eq2

again putting n = n-1 in eq2

T(n-2) = T(n-3)*(n-2)…..eq3

putting eq2 –> eq1

T(n) = T(n-2)*(n-1)*n…..eq4

putting eq3 –> eq4

T(n) = T(n-3)*(n-2)*(n-1)*n

.

.

T(n) = T(n-k)*(n-(k-1))*……*(n-1)*n

putting,

n-k = 1 or

k = n -1

T(n) = T(n-(n-1))*(n-(n-1-1))*……*(n-1)*n

T(n) = 1*2*3*……*(n-1)*n

T(n) = O(n!)

Why? Because, 1*2*3*……*(n-1)*n = n!

or

T(n) = O(n!) ≈  O(nn)

Conclusion:

In substitution method, we mathematically solve the problem. Hence, this method is time consuming, but you need to understand this because sometimes you have a recurrence relation and you need to evaluate the answer using substitution method.

For,

Recursion Tree Method( Iteration Method) click here!

Master Theorem click here!