The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
4.2k views

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));
}
  1. $O(n)$
  2. $O(n \log n)$
  3. $O(n^2)$
  4. $O(2^n)$
asked in Algorithms by Veteran (59.6k points)
edited by | 4.2k views

4 Answers

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

answered by Boss (22.3k points)
edited by
+2
You explain well - all points included :)

HTML spacing for alignment is bad- even if we align spaces properly when the screen resolution changes it becomes bad. Latex is better :)
+1
Thank you sir :) . I will try to improve next time.
0
It will be (2^k)-1
+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)$
answered by Boss (14.3k points)
0
@Bhagirathi: why this 1 after 2T(n-1)
+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.
 

+1
No it's not for that. 1 in the recursive equation signifies that some work has been done to divide a problem into two subproblems.

Base condition if(n==1) return 1 is used at the end.
0
@amitatgateoverflow is correct.

1 or some constant term is there to denote the amount of work to be done to divide the original problem and then combine the solutions to those subproblems to get the final answer.
+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(n0 . 2n/1) = O(2n) Option (d)

Reference : https://www.google.co.in/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwiapt6kxLXTAhVCOo8KHVOMCLYQFggiMAA&url=https%3A%2F%2Fwww.eecis.udel.edu%2F~saunders%2Fnotes%2Frecurrence-relations.pdf&usg=AFQjCNEDfKzz_SaGkG9uYob8-Ut4qV7jww&sig2=MZlwUU2OTfrZF0p_6ddVbA

answered by Boss (13.8k points)
0
how could we know 'd ' value.
0

Read the theorem statement again and you would know.

F(n) is in O(nd)

+3 votes

Another way to visualize this problem.

answered by Active (2k points)
0
F(2) = 2 ??? how ??
0
@Puja Mishra You can find that easily by putting $n = 2$ in the code. The $return$ part in the $else$ block will return $recursive(1) + recursive(1)$.


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,748 questions
47,471 answers
145,586 comments
62,234 users