Question

The recurrence eqation:
T(1) = 1
T(n) = 2T(n - 1) + n, n $\ge$ 2

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

Answer 1

The correct option is A 2${}^{n+1}$ - n -2

T(1) = 1
T(n) = 2T(n - 1) + n n $\ge$ 2
T(2) = 2T(1) + 2 = 2.1 + 2 = 4
T(3) = 2T(2) + 3 = 2.4 + 3 = 11
T(4) = 2T(3) +4 = 2.11 + 4 =26

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