Q74

MCQ2 marks, −0.5

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

(A)

$\Theta(n)$ and $\Theta(n)$

(B)

$\Theta(2^n)$ and $\Theta(n)$

(C)

$\Theta(n)$ and $\Theta(2^n)$

(D)

$\Theta(2^n)$ and $\Theta(2^n)$

Loading…