Question

Write down the run time of the following recursive functions as a recurrence relation:

int f( int n ) {

if ( n <= 1 ) {

return 1;

}

return f( n – 1 ) + f( n – 1 );

}

Answer 1

recurrence relation for the given function f is
f(n) = 2f(n-1) + 1
    = 2(2f(n-2)+1) + 1
    = 2^2f(n-2)+2 + 1
    = 2^3f(n-3)+ 2^2 +2 + 1
    .....
    .....
    = 2^nf(n-n)+ ... + 2^2 +2 + 1
    = 2^nf(0)+ ... + 2^2 +2 + 1
    = 2^n+ ... + 2^2 +2 + 1
    = 2^(n+1)
    = O(2^n)

the run time of the following recursive functions as a recurrence relation is O(2^n)