HTML spacing for alignment is bad- even if we align spaces properly when the screen resolution changes it becomes bad. Latex is better :)

18 votes

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)); }

- $O(n)$
- $O(n \log n)$
- $O(n^2)$
- $O(2^n)$

32 votes

Best answer

**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 \Bigl [ 2T(n - 2) + a \Bigr ] + a &= 4T(n - 2) + 2a + a \\[1em]

&= 4 \Bigl [ 2T(n - 3) + a \Bigr ] + 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} + \Bigl ( 2^{n - 1} - 1 \Bigr ) a \\ = O(2^n)$$

16 votes

Its similar to tower of hanoi problem

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

T(1)=1

T(2)=2.1 + 1 =3

T(3)=2.3 +1 =7

T(4)=2.7 +1 =15 .... .....

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

we can see that its a pattern getting formed which is $t(n)=2^n-1$ so it is d $O(2^n)$

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

T(1)=1

T(2)=2.1 + 1 =3

T(3)=2.3 +1 =7

T(4)=2.7 +1 =15 .... .....

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

we can see that its a pattern getting formed which is $t(n)=2^n-1$ so it is d $O(2^n)$

1

@Gate Mm:

T(n) = 2T(n-1)+1. Here +1 is for the base condition **if(n==1) return 1**. It has the constant time complexity of 1.

9 votes

The recurrence relation from the code is :

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

The above recurrence can be solved easily with the help of **Subtract and conquer master's theorem**.

Here a=2, b=1 d=0

Since a>1, the third case applies

**O(n ^{0} . 2^{n/1}) = O(2^{n}) Option (d)**

3 votes

1 vote

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

$a_{n}=2a_{n-1}+1$

**First solve this**

$a_{n}=2a_{n-1}$

$r^n=2r^{n-1}$

$\dfrac{r^n}{r^{n-1}}=2$

$r=2$

$a_{n}^{(h)}=d(2)^n...........(1)$

**Now solve this**

$a_{n}^{(p)}=p_{0}$

$a_{n}=2a_{n-1}+1$

$a_{n}-2a_{n-1}=1$

$p_{0}-2(p_{0})=1$

$p_{0}=-1$

$a_{n}^{(p)}=-1...........(2)$

$Add\ (1)+(2)$

$a_{n}=d(2^n)-1............(3)$

$Given\ a_{1}=1$

$Substitute\ in\ (3)$

$d=1$

$a_{n}=1.(2^n)-1$

$T(n)=O(2^n)$