recurrence equation:

Question

T(1) = 1 T(n) = 2T(n - 1) + n, n ≥ 2 evaluates to

(a) 2n + 1 - n – 2

(b) 2n – n

(c) 2n + 1 – 2n – 2

(d) 2n – n     

HOW TO EVALUATES USING MASTER THEOREM

Comments

To apply Master's Theorem, the function should be of the form aT(n/b) + f(n) where a>=1, b>1.

I believe MT won't be applicable here.

Answer 1

You can do it without using Master's theorem.

Just do repeated substitutions.

After $k$ iterations, your recurrence will be:

$T(n) = 2^k\times T(n-k) + n(1 + 2 + 4 + \dots + 2^k)$.

The base case for this is satisfied when $n - k = 1$ or $k = n -1$.
You can substitute this in the original equation to get the answer in terms of $n$.