GATE CSE 2004 | Question: 83, ISRO2015-40

Question

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

• A. $O(n)$
• B. $O(n \log n)$
• C. $O(n^2)$
• D. $O(2^n)$

Answer 1

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

Comments

It will be (2^k)-1

---

Indirectly they are asking tower of hanoi time complexity.

---

can we write θ(\(2^{n}\))?

Answer 2

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 $O(2^n)$

Answer : $D.$ $O(2^n)$

Comments

@Bhagirathi: why this 1 after 2T(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.
 

---

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.

---

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

Answer 3

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  $3^{rd}$ case applies

$O(n^0 . 2^{n/1}) = O(2^n)$ 

Answer : $D. O(2^n)$ 

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

Comments

Sir can we solve it by finding homogenous and particular solution?

Answer by that method :: (2^n)-1. Is that correct?

---

yes you can do it that way too , but it would be a lengthy way to solve . Single term recurrence relation is advised to be solved by substitution or tree method.

---

@Ayush Upadhyaya Sir This will fail if

T(n)=2T(n-1)+n , n>1 and T(1)=1

Answer 4

Another way to visualize this problem.

Comments

F(2) = 2 ??? how ??

---

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

Answer 5

Answer : Option D

Answer 6

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

Comments

Correct procedure. For those who want to learn more, check the below link :

https://www.eecs.yorku.ca/course_archive/2008-09/S/1019/Website_files/21-linear-recurrences.pdf