**Recurrence relation in DAA**

The model that uses mathematical concepts to calculate the time complexity of an algorithm is known as the recurrence relational model.

A recursive relation, T(n), is a recursive function of integer n. Every recursive function consists of both recursive and base cases.

The section of the definition that does not contain T is called a base case of the recurrence relation, and the portion that contains T is called recursive or recursive relation.

Recurrence relations are very useful in calculating the running time complexities of recursive algorithms.

**Example:**

A Fibonacci sequence is defined by the recurrence relation – Fn = F(n-1) + F(n-2)

with initial conditions f1=1 and f2 = 1.

**Example:** Write the recurrence relation for the following method.

1 2 3 4 5 6 7 8 |
void f(int n) { if (n > 0) { cout << n; f(n-1); } } |

The base case is reached when n == 0. The method performs one comparison. Thus, the number of operations when n==0, T(0), is some constant a.

When n > 0, the method performs two basic operations and then calls itself, using ONE recursive call, with a parameter n – 1.

Therefore the recurrence relation is:

T(0) = a where a is constant

T(n) = b + T(n-1) where b is constant, n > 0

**Solving recurrence relation**

The following are the ways to solve a recurrence relation :

- Recursion Tree method
- Substitution method
- Master method

**SUBSTITUTION METHOD**

In the substitution method, we make a guess for the solution, and then we use mathematical induction to prove the guessed answer is right or wrong.

For example, Let us take the recurrence T(n) = 2T(n/2) + n

We guess the solution as T(n) = O(nLogn). Now we use induction

to prove our guess.

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

**RECURRENCE TREE METHOD**

In the recurrence tree method, a recurrence tree is drawn and calculates the time taken by every level of a tree. After analyzing each level, we sum up the work done at all levels. In order to draw a recurrence tree, start from the given recurrences and keep drawing till we find a pattern among all the levels. The pattern follows arithmetic or geometric series.

For example, consider the recurrence relation.

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

cn2

/ \

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

If we further break down the branches 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 the tree further gives us the following result

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. The following series – T(n) = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + …. is obtained

on analyzing the end levels of the tree.

The above series is a geometric progression with a ratio of 5/16. We can sum the infinite series by calculating an upper bound.

We get the sum as (n2)/(1 – 5/16), which is having a time complexity of O(n2).

**MASTER METHOD**

We can get an immediate solution using the master method. The master method only works on the recurrence relations that can be transformed into the following relation:

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

There are following three cases:

**1.** If f(n) = Θ(n^{c})

if c < Log_{b}a then T(n) = Θ(Log_{b}a^{n})

**2.** If f(n) = Θ(n^{c})

if c = Log_{b}a then T(n) = Θ(n^{c}Log n)

**3.**If f(n) = Θ(n^{c})

if c > Log_{b}a then T(n) = Θ(f(n))

**How does this work?**

The master method is basically the derivation of the recurrence tree method. After drawing the recurrence tree of recurrence relation, T(n) = aT(n/b) + f(n),

we can observe that the task done at root is f(n) and task done at all leaves is Θ(nc) where c is Log_{b}a. And the height of the recurrence tree is Log_{b}n.

For example,

Merge sort – T(n) = 2T(n/2) + Θ(n). The relation falls in **2** as c is 1 and Log_{b}a ] is also 1. So the solution is Θ(n Logn)

Binary search: T(n) = T(n/2) + Θ(1). This relation falls in **2** as c is 0 and Log_{b}a is also 0. So the solution is Θ(Logn).