edited by
19,272 views

6 Answers

Best answer
49 votes
49 votes

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

edited by
23 votes
23 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)$
13 votes
13 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

5 votes
5 votes

Another way to visualize this problem.

Answer:

Related questions

47 votes
47 votes
7 answers
1
Kathleen asked Sep 18, 2014
17,345 views
The recurrence equation$ T(1) = 1$$T(n) = 2T(n-1) + n, n \geq 2$evaluates to$2^{n+1} - n - 2$$2^n - n$$2^{n+1} - 2n - 2$$2^n + n $
53 votes
53 votes
4 answers
3
48 votes
48 votes
2 answers
4
Kathleen asked Sep 23, 2014
22,554 views
If one uses straight two-way merge sort algorithm to sort the following elements in ascending order: $20, \ 47, \ 15, \ 8, \ 9, \ 4, \ 40, \ 30, \ 12, \ 17$then the o...