GATE CS 2015 Set 2 Q11 — Asymptotic Worst Case Time and Space Complexity

Consider the following C function.

int fun(int n) {
    int x=1, k;
    if (n==1) return x;
    for (k=1; k<n; ++k)
        x = x + fun(k) * fun (n-k);
    return x;
}

The return value of $fun(5)$ is ______.

View worked solution

Answer: 51

Let $T(n)$ denote the return value of fun(n). We can analyze the function and write the recurrence relation for $T(n)$ as follows:

For $n = 1$ , the base case is triggered:
$T(1) = 1$
For $n > 1$ , the loop calculates:
$T(n) = 1 + \sum_{k=1}^{n-1} T(k) \cdot T(n-k)$

Let us compute the values step-by-step:

For $n = 2$ :
$T(2) = 1 + T(1) \cdot T(1) = 1 + (1 \cdot 1) = 2$
For $n = 3$ :
$T(3) = 1 + T(1) \cdot T(2) + T(2) \cdot T(1) = 1 + (1 \cdot 2) + (2 \cdot 1) = 5$
For $n = 4$ :
$T(4) = 1 + T(1) \cdot T(3) + T(2) \cdot T(2) + T(3) \cdot T(1) = 1 + (1 \cdot 5) + (2 \cdot 2) + (5 \cdot 1) = 15$
For $n = 5$ :
$T(5) = 1 + T(1) \cdot T(4) + T(2) \cdot T(3) + T(3) \cdot T(2) + T(4) \cdot T(1)$
$T(5) = 1 + (1 \cdot 15) + (2 \cdot 5) + (5 \cdot 2) + (15 \cdot 1)$
$T(5) = 1 + 15 + 10 + 10 + 15 = 51$

Thus, the return value of fun(5) is 51.

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

Published 10 Oct 2026

Related questions