Question

Consider the following two 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

Accepted Answer

The correct answer is (B) Θ(2ⁿ) and Θ(n). f1 makes two unmemoized recursive calls per invocation with only a constant reduction in n each time, giving the exponential recurrence T(n)=T(n-1)+T(n-2)+O(1), i.e. Θ(2ⁿ)-class growth. f2 computes the same underlying values bottom-up in a single loop from 2 to n, doing O(1) work per iteration — Θ(n).

Explanation