Official PYQ · 2008Q74Asymptotic Worst Case Time and Space ComplexityMCQ1 mark

GATE CS 2008 Q74 — Asymptotic Worst Case Time and Space Complexity

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

View worked solution

Answer: B

To find the running time of both functions, we analyze their control flow and recurrence relations:

1. Analysis of $f1(n)$

The function $f1(n)$ is a recursive function. Let $T(n)$ be the number of steps (or time complexity) taken by $f1(n)$ for an input $n$ .

For $n \ge 2$ , the function makes two recursive calls: one to $f1(n-1)$ and another to $f1(n-2)$ , along with a constant number of basic operations.

The recurrence relation is:

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

with base cases $T(0) = c_0$ and $T(1) = c_1$ .

This recurrence is of the same form as the Fibonacci sequence recurrence. Solving the characteristic equation $r^2 - r - 1 = 0$ gives the golden ratio $\phi = \frac{1 + \sqrt{5}}{2} \approx 1.618$ .

Thus, the tight bound is:

T(n) = \Theta(\phi^n) \approx \Theta(1.618^n)

Since any exponential growth of the form $a^n$ (where $a > 1$ ) is asymptotically categorized under exponential time, it is represented as $\Theta(2^n)$ in standard multiple-choice options.

2. Analysis of $f2(n)$

The function $f2(n)$ is an iterative implementation using dynamic programming (memoization with arrays):

Array initializations take $O(1)$ time.
The for loop runs from $i = 2$ to $n$ .
Inside the loop, all operations (array lookups, additions, and multiplications) take constant time, i.e., $O(1)$ .