GATE CSE 2004 | Question: 84

Question

The recurrence equation
$ T(1) = 1$
$T(n) = 2T(n-1) + n, n \geq 2$

evaluates to

• A. $2^{n+1} - n - 2$
• B. $2^n - n$
• C. $2^{n+1} - 2n - 2$
• D. $2^n + n $

Comments

Initial equation should be T(0)=1 not T(1) =1.

---

what role does the condition given play that n>=2 ?

---

@Arjunsir @GO Classes does this recurrence fail the regularity condition? 

---

Simple trick here is just check for T(1) = 1 or not
 

by checking options we can simply state that none other than option a is correct!

Answer 1

$T(n) = 2T(n-1) +n, n \geqslant 2 , T(1) = 1$

$  T(n)    = n + 2(n-1) + 2^2 (n-2) + \dots + 2^{(n-1)}(n -(n-1))$

           $=n( 1 + 2 + \dots + 2^{n-1}) - (1.2 + 2.2^{2} +3.2^{3}+\dots+ (n-1).2^{n-1})$

           $=n(2^n-1) -(n.2^n-2^{n+1}+2)$

           $=2^{n+1}-n -2$

Correct Answer: $A$

Comments

@shankargadri yes we can do like that , it’s time saver !!

---

@Arjun sir, here subtract and conquer is failing..Could you explain why?

---

just put 2 and (3 for safe side) and get the value and check the options by putting same 2 and 3 thats it answer will come as option A

Answer 2

$T(1) = 1$
$T(2) = 4$
$T(3) = 11$
$T(4) = 26$
$T(5) = 57$
$T(6) = 120$
$T(7) = 247$

So, $T(n) = 2^{n+1} - n - 2$

Comments

@pranavbhosle_ they are talking about master theorem for decreasing functions a.k.a subtract and conquer.They are not talking about divide and conquer

---

@Apoorva Jain

Muster theorem works fine here. But keep in mind that, both master and Muster theorems give the asymptotic bounds, not the exact evaluation. 

For finding exact evaluation, either go with substitution method or by solving Linear Non-Homogenous Recurrence Relations.

Correct me if I am wrong

---

Thank you <100 !

Answer 3

Given that $T(1) =1$ //OMG here itself Option C & D fails now check A & B

$T(2)=2T(1)+n=2+2=4$  //Option $B$ evaluates to $2$ so it is wrong

Hence Option $A$ is answer.

Comments

Nice reasoning for option C and D! Found useful!

---

Quickest way to solve this problem.

---

NICE

Answer 4

Here, $T(1)=1$ and

$$\begin{align} T(n)&=2T(n-1)+n\\&=2^2T(n-2)+2(n-1)+n;~[\text{Putting }T(n-1)=2T(n-2)+(n-1)]\\&=2^3T(n-3)+2^2(n-2)+2(n-1)+n;~[\text{Doing so}]\\&=\cdots\\&=2^{n-1}T(n-(n-1))+2^{n-2}\{n-(n-2)\}+2^{n-3}\{n-(n-3)\}+\cdots+2(n-1)+n\\&=2^{n-1}T(1)+2^{n-2}(2)+2^{n-3}(3)+\cdots+2^{1}(n-1)+2^{0}n\end{align}$$

 

Now putting $T(1)=1$ as given,

$$\begin{align}\therefore T(n)&=2^{n-1}(1)+2^{n-2}(2)+2^{n-3}(3)+\cdots+2^{1}(n-1)+2^{0}n \tag{i} \\ \Rightarrow 2T(n)&=2^n(1)+2^{n-1}(2)+2^{n-2}(3)+\cdots+2^2(n-1)+2^{1}n \tag{ii}\end{align} $$

 

$$\mathrm{no(ii)}-\mathrm{no(i)}\Rightarrow\\ \begin{align}T(n)&=2^n+2^{n-1}(2-1)+2^{n-2}(3-2)+\cdots+2^1(n-(n-1))-2^{0}n\\&=(2^{n}+2^{n-1}+2^{n-2}+\cdots+2)-n\\&=(2+2^2+2^3+\cdots+2^{n-1}+2^n)-n; ~[\text{Rearranging}]\\&=\frac{2(2^n-1)}{2-1}-n;~[\scriptsize\because a+ar+ar^2+\cdots+ar^n=\frac{a(r^{n+1}-1)}{r-1}\text{ as Geometric Series}]\\&=2^{n+1}-2-n \end{align}$$

 

$\therefore T(n)=2^{n+1}-n-2$.

 

So the correct answer is A.

Comments

Best Explanation

---

Best answer! Thank you so much!

---

awesome!

Answer 5

solution .

Comments

this is what i was looking for ,, thanx buddy :)

---

@varun singh

you have written

T(n-k) = 2T(n-(k-1)) + (n-k)

so  for k=2

T(n-2) = 2T(n-(2-1)) + (n-2)

T(n-2) = 2T(n-1) + (n-2)

so it should be

T(n-k) = 2T(n-(k+1)) + (n-k)

please look into it and if i am wrong please do correct me.

---

Yes @pramodborana112 u are right ,  it should be T(n-k) = 2T(n-(k+1)) + (n-k), but everything else are correct.

---

I think  there would be change in arithmetric geometric expression  then as k =n-2 then in that case  how would we solve

Answer 6

T(2) = 4.

Option A.

Solved under 30 seconds.

Comments

Nice approach!