GATE CS 2004 Q83 — Asymptotic Worst Case Time and Space Complexity

The time complexity of the following C function is (assume $n > 0$ )

int recursive (int n) {
    if(n == 1)
        return (1);
    else
        return (recursive (n-1) + recursive (n-1));
}

View worked solution

Answer: D

To find the time complexity of the given recursive function, let $T(n)$ represent the number of operations performed for an input $n$ .

From the code, we can formulate the recurrence relation as follows:

Base case: For $n = 1$ , the function performs a constant number of operations:
$T(1) = heta(1)$
Recursive step: For $n > 1$ , the function makes two recursive calls to recursive(n-1) and performs a constant-time addition:
$T(n) = 2T(n-1) + heta(1)$

Let us solve this recurrence relation using substitution:

\begin{align*}T(n) &= 2T(n-1) + c \\&= 2(2T(n-2) + c) + c = 2^2T(n-2) + (2 + 1)c \\&= 2^2(2T(n-3) + c) + (2 + 1)c = 2^3T(n-3) + (2^2 + 2 + 1)c \\&\ \ \vdots \\&= 2^{n-1}T(1) + c \sum_{i=0}^{n-2} 2^i \\&= 2^{n-1}T(1) + c(2^{n-1} - 1)\end{align*}

Since both terms are dominated by $2^n$ , the time complexity is:

T(n) = O(2^n)

Hence, the correct option is D.

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

Published 10 Oct 2026

Related questions