Consider the following C functions:
int f1 (int n)
{
if(n == 0 || n == 1)
return n;
else
return (2 * f1(n-1) + 3 * f1(n-2));
}
int f2(int n)
{
int i;
int X[N], Y[N], Z[N];
X[0] = Y[0] = Z[0] = 0;
X[1] = 1; Y[1] = 2; Z[1] = 3;
for(i = 2; i <= n; i++){
X[i] = Y[i-1] + 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
- $\Theta(n)$ and $\Theta(n)$
- $\Theta(2^n)$ and $\Theta(n)$
- $\Theta(n)$ and $\Theta(2^n)$
- $\Theta(2^n)$ and $\Theta(2^n)$