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

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

+23 votes

Best answer

**Option is 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 \qquad \to (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 \\&\vdots \\&= 2^kT(n-k) + (2^{k}-1) a \end{align*} \qquad \to (2)$

On Substituting Limiting Condition

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

Therefore, equation $(2)$ becomes:

$\quad 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)$

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

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.6k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.3k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 480
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,748 questions

47,471 answers

145,586 comments

62,234 users