Made easy Workbook 2020

Question

Question:

$T(1)=1$

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

evaluates to?

Can anyone solve it by substitution method?

---

Given answer 

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

How? 

Comments

O(2^n)

---

What I think is that if you try to somehow convert the expression you are getting into the given answer it's not easy and not obvious. The question seems like selection and elimination type. If you have four options then successively find out values, say upto T(5), and see which option's result is matching with your result.

There will be a way to adjust the expression by adding or subtracting some terms to get the answer but it will be cubersome.

---

https://gateoverflow.in/19033/t-c-of-t-n-2t-n-1-n-n-1-t-1-1 

Derivation of these problem

Answer 1

TRICK

put any value in question and answer....if they match then correct solution

 

otherwise solve with substitution method... then you will get the answer

Answer 2

The answer should be approx O(n 2^n). Yours answer comes only O(2^n).... Which is wrong for sure.

Answer 3

Solve the by hit and trial method

Put the n= 2

We find  T(2)= 2T(2-1) +2

                        = 2*1+2=4

And the check options is equal to 4

So options (a) is correct