The GATE Grind

GATE 2008 CS – Question 74

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · MTA

Consider the C functions (assume N>n):

int f1(int n) {
 if(n==0 || n==1) return n;
 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];
}

What are the running times of f1(n), f2(n)?

  1. $\Theta(n)$ and $\Theta(n)$
  2. $\Theta(2^n)$ and $\Theta(n)$
  3. $\Theta(n)$ and $\Theta(2^n)$
  4. $\Theta(2^n)$ and $\Theta(2^n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: MTA

Explanation

We are sorry we couldn't write detailed soluition for this, we are working on it!, please consider asking your own AI, its just 2-3 clicks with very minimum effort

More Asymptotic Analysis and Time/Space Complexity questions

All Asymptotic Analysis and Time/Space Complexity questions →