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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+14 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)$

+27 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.

+8 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)**

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.1k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.6k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

49,845 questions

54,783 answers

189,422 comments

80,416 users