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

GATE CS 2008 Q75 — 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];
}

$f1(8)$ and $f2(8)$ return the values

View worked solution

Answer: C

We can find the values returned by both functions by tracing them step-by-step.

1. Evaluating $f1(8)$ :

The recurrence relation for $f1(n)$ is:

f1(n) = \begin{cases} n & \text{if } n = 0 \text{ or } n = 1 \\ 2 \cdot f1(n-1) + 3 \cdot f1(n-2) & \text{if } n \ge 2 \end{cases}

Let's compute the values sequentially:

$f1(0) = 0$
$f1(1) = 1$
$f1(2) = 2(1) + 3(0) = 2$
$f1(3) = 2(2) + 3(1) = 7$
$f1(4) = 2(7) + 3(2) = 20$
$f1(5) = 2(20) + 3(7) = 61$
$f1(6) = 2(61) + 3(20) = 182$
$f1(7) = 2(182) + 3(61) = 364 + 183 = 547$
$f1(8) = 2(547) + 3(182) = 1094 + 546 = 1640$

2. Evaluating $f2(8)$ :

The iterative function $f2(n)$ maintains three arrays where $Y[i] = 2X[i]$ and $Z[i] = 3X[i]$ . Substituting these into the recurrence for $X[i]$ gives:

X[i] = Y[i-1] + Z[i-2] = 2X[i-1] + 3X[i-2]

Since the base cases are $X[0] = 0$ and $X[1] = 1$ , the sequence generated by $X[i]$ is identical to the sequence generated by $f1(i)$ .

Thus, $f2(8) = X[8] = 1640$ .

Therefore, both $f1(8)$ and $f2(8)$ return $1640$ .

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

Browse this topic

More Asymptotic Worst Case Time and Space Complexity questions

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

Related questions