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)
- A.
θ(n) and θ(n)
- B.
θ(2n) and θ(n)
- C.
θ(n) and θ(2n)
- D.
θ(2n) and θ(2n)
Attempted by 52 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.