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

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

Answer 2

Answer : Option D