PA of Algorithms Q58

0. Consider the following C functions:

int f l(int n)
{
if(n = = 0 || n = = 1) return n;
else return (2* f1( n –1) + 3 * f1(n – 2));
}
intf2 (int n)
{ int i;
int X[N], Y[N], Z[N];
X[1] = 1; Y[1] = 2;Z[1] = 3;
for( i = 2; i < = n ; i ++ )
{
X[i]=Y[i-l] + Z[i-2];
Y[i]=2*X[i];
Z[i] = 3*X[i];
}
return X[n] ;
}
The running time of f1(n) and f2(n) are

Answer
Comment
Array

Option : B
Explanation :
Recurrence relation for f1()is
T (n) = 2T (n–1) + 3 T (n–2)
After solving it would be Θ(1.6)ⁿ) so the largest
value among the options is Θ(2ⁿ).
f2() is simple loop executed n times.
So Θ(n)

Forgot your password?

I agree with the Terms.