In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms.

Recurrence relations are used to determine the running time
of recursive programs – recurrence relations themselves are
recursive.

T(0) = Time to solve problem of size 0

T(n) = Time to solve problem of size n

There are many ways to solve a recurrence relation running time:

1) Back substitution

2) By Induction

3) Use Masters Theorem

4) Recursion tree

**Examples of recurrence relations:**

- T( n ) = T(n -1) + 1, T( 0 ) = 1
- F( n ) = F(n -1) + F(n-2) , F(1) =1 , F(0) = 1 Fibbanocci Sequence
- a
_{n}= a_{n-1}+ 3 , a_{0}=5 - 5, 8, 11, 14, 17, 20, 23, ...

This is a tutorial on solving a recurrence relation using the substitution method.

Download PDF
Example: T(n) = 4T(n/2) + n

Reading from the equation, a = 4, b=2, f(n) = n^{1}, so d = 1.

d < log_{b}a = 1 < log_{2}4

so n = O( n^{log24}) = O( n^{2} )

Site PDF

Solve recurrence relation using Master Theorem

Site/* C Program for simple recursion */ /* By: Rodney Anderson */ # include < stdio.h > int T( int n); // Defining function T(). int main(void) { int n = 8; int i; for(i=0; i < n; i++) { printf("T(%d) = %d\n", i, T(i) ); // prints 5, 8, 11, 14, 17, 20, 23, 26 } //Comment out the system("pause") if you are not using Windows system("pause"); } int T( int n) { if( n == 0) return 5; else return T(n-1) + 3; }