Answer is (D) $O(2^n)$
int recursive (int n) {
if(n == 1) // takes constant time say 'A' time
return (1); // takes constant time say 'A' time
else
// takes T(n-1) + T(n-1) time
return (recursive (n-1) + recursive (n-1));
}
$T(n) = 2T(n - 1) + a$ is the recurrence equation found from the pseudo code. Note: $a$ is a constant $O(1)$ cost that the non-recursive part of the function takes.
Solving the recurrence by Back Substitution:
$$\begin{align*}
T(n) &= 2T(n - 1) + a \\[1em]
T(n - 1) &= 2T(n - 2) + a \\[1em]
T(n - 2) &= 2T(n - 3) + a \\[1em]
&\vdots
\end{align*}$$
Thus, we can re-write the equation for $T(n)$ as follows
$$\begin{align*}
T(n)
&= 2 \left [ 2T(n - 2) + a \right ] + a &= 4T(n - 2) + 2a + a \\[1em]
&= 4 \left [ 2T(n - 3) + a \right ] + 3a &= 8T(n - 3) + 4a + 2a + a \\[1em]
&\vdots \\[1em]
&= 2^k T(n - k) + (2^k - 1) a
\end{align*}$$
On Substituting Limiting Condition
$T(1) = 1 \\
\implies n - k = 1 \\
\implies k = n - 1
$
Therefore, our solution becomes
$$2^{n - 1} + \left ( 2^{n - 1} - 1 \right ) a \\ = O(2^n)$$