GATE EXAM PREPARATION IN "C" -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) Θ(n) and Θ(n)
(B) Θ(2^n) and Θ(n)
(C) Θ(n) and Θ(2^n)
(D) Θ(2^n) and Θ(2^n)

Answer (B)
For f1(), let T(n) be the function for time complexity.

  T(n) = T(n-1) + T(n-2) 

Above recursion is a standard one for Fibonacci Numbers. After solving the recursion, we get

 T(n) = 1/sqrt(5)[(1 + sqrt(5))/2]^n - 1/sqrt(5)[(1 - sqrt(5))/2]^n 

Above recursion can also be written as Θ(1.618.^n)

In f2(), there is a single loop, so time complexity is Θ(n)

Among all the 4 given choices, (B) looks closest