Consider the following C program int f1(int n) { if(n == 0 || n == 1) return…

2008

Consider the following C program 

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)

Answer: B. θ(2n) and θ(n) — Answer summary: the naive recursive routine runs in exponential time, while the iterative routine runs in linear time. Reasoning for the recursive routine:…

  1. A.

    θ(n) and θ(n)

  2. B.

    θ(2n) and θ(n)

  3. C.

    θ(n) and θ(2n)

  4. D.

    θ(2n) and θ(2n)

Attempted by 57 students.

Show answer & explanation

Correct answer: B

Answer summary: the naive recursive routine runs in exponential time, while the iterative routine runs in linear time.

Reasoning for the recursive routine:

  • Let T(n) denote the running time of the recursive function. Each call at n (for n>1) makes two recursive calls: one on n-1 and one on n-2, plus O(1) work for the arithmetic and tests.

  • Thus the recurrence is T(n) = T(n-1) + T(n-2) + O(1). This is the same form as the Fibonacci recurrence for the number of calls, whose solution grows as Theta(phi^n), where phi = (1+sqrt(5))/2 ≈ 1.618.

  • Therefore the running time is exponential: Theta(c^n) (more precisely Theta(phi^n)).

Note about the function value vs runtime:

  • The mathematical sequence defined by f1 satisfies f(n)=2f(n-1)+3f(n-2), whose closed-form grows like 3^n (so the function values grow exponentially with base 3). However, the running time of the naive recursive implementation is determined by the number of recursive calls and is Theta(phi^n).

Reasoning for the iterative routine:

  • The second function initializes arrays and then runs a single for-loop from i = 2 to n performing a constant amount of work per iteration (a few assignments and arithmetic operations).

  • Therefore its running time is Theta(n).

Final conclusion:

  • Recursive routine (f1): exponential time Theta(phi^n) (i.e., exponential).

  • Iterative routine (f2): linear time Theta(n).

Therefore, the correct choice is the one that states the first routine is exponential and the second is linear.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…