Discrete Mathematics

Recurrence Relation

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:

  1. T( n ) = T(n -1) + 1, T( 0 ) = 1
  2. F( n ) = F(n -1) + F(n-2) , F(1) =1 , F(0) = 1 Fibbanocci Sequence
  3. an = an-1 + 3 , a0=5
  4. 5, 8, 11, 14, 17, 20, 23, ...


Solve recurrence Relation By Iterative Substitution

randerson112358

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

Download PDF


Solve Recurrence Relation Proof by iteration

Solve Recurrence Relation Masters Theorem


Example: T(n) = 4T(n/2) + n
Reading from the equation, a = 4, b=2, f(n) = n1, so d = 1.
d < logba = 1 < log24
so n = O( nlog24) = O( n2 )

Site PDF



Solve recurrence relation by Master Theorem

randerson112358

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;
    }


Copyright © 2013, Everything Computer Science.