IISC DS and AI sample paper

Question

int func(int n)

{

if(n <= 1)

return n;

else

return 3*func(n-3) - 3*func(n-2);

 }

The running time of the above function is

Answer 1

 

This is a recursive function, as func() is called inside func().

So we will write recurrence relation for it.

Assume T(n) is time complexity of func(n)

then,

$T(n) =\begin{Bmatrix} C, if(n≤1)\\T(n-3)+T(n-2)+C, if(n>1) \end{Bmatrix}$ 

 

Where C is the constant time taken by each recursive call to perform a return or an addition or a multiplication operation.

 

Now, solve it using recursive tree method.

T(n)=O($2^{n/2}$)

Or

T(n)=$\Omega$($2^{n/3}$)

 

 

I hope you got it.

Thank you.