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? 

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

any one can tell me what is time complexity exist it  i.e. O(?)

it is O(2^n). 

---

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

---

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

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

nice trick :)

---

excellent trick bro

---

Smart method

---

is it required that we go till 7 value i put n=2 and get 4 then check ans which gave me 4 by putting n=2 only A option satisfied it..

---

@Arjun

sir by applying muster theorem or subtract and conquer master theorem

ans comes out to be proportional to n*(2^n) .

Why it's far different from actual answer ?  Do muster theorem has any condition where it fails ?

Plz help.

---

EXCELLENT !!

Does this technique works for every recurrence relation ?

---

Yes, if options are given

---

@Apoorva Jain same doubt do you got any answer?

---

Yeah , mine is same doubt, if you got any answer plz let me know.

---

very nice trick sir...

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

Comments

Nice reasoning for option C and D! Found useful!

---

Quickest way to solve this problem.

Answer 4

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