The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

+21 votes

Best answer

**Option D**

int recursive (int n) { if(n == 1) // takes constant time say 'A' time return (1); // takes constant time say 'A' time else return (recursive (n-1) + recursive (n-1)); // takes T(n-1) + T(n-1) time }

$T(n) = 2T(n-1) +a$ is the recurrence equation found from the pseudo code .

Solving the Recurrence Equation By Back Substitution Method

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

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

$T(n-2) = 2T ( n-3)+a$

We can re write Equation 1 as

$\begin{align*}T(n) &= 2 [2T ( n-2)+a ] +a = 4T(n-2)+ 3a \\ &= 2[2T ( n-3)+a] + 3a = 8T (n-3) + 7a \\&\dots \\&= 2^kT(n-k) + (2^{k}-1) a \end{align*}$ ------ (Equation 2)

On Substituting Limiting Condition

$T(1) = 1$ implies $n-k = 1 \\ \implies k= n-1$

Therefore Equation 2 becomes

$2^{ n-1} +(2^{n-1}-1)a = O(2^n)$

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

@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.

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 279
- Exam Queries 396
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 7

33,688 questions

40,231 answers

114,272 comments

38,803 users