time complexity

Question

The recurrence equation

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

evaluates to $a.2^{n+1} - bn - c$, what is the value of $100a+ 10b+c$?

Answer 1

$T(1) = 1$

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

So, $T(2) = 2+2=4, T(3) = 11. T(4) = 26$.

We are given, $T(n) = a.2^{n+1} - b.n - c$

So,

$T(2) = 4 \implies 8a - 2b - c = 4 \rightarrow(1)$

$T(3) = 11 \implies 16a - 3b - c = 11 \rightarrow(2)$

$T(4) = 26 \implies 32a - 4b - c = 26 \rightarrow(3)$

$(2) - (1) \implies 8a - b = 7 \rightarrow(4)$

$(3)-(2) \implies 16a - b = 15 \rightarrow(5)$

$(5) - (4) \implies 8a = 8, a = 1$

Now, from $(4)$, we get $b = 1$.

From $(1)$ we get $c = 2$.

So, $100a + 10b + c = 112$.

---

Now, lets solve by recurrence.

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

This is an AGP series with $d=1$ and $r= 0.5$. But I'm not using its properties. Multiplying (1) by 2 gives,

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

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

$\because 2^1 + 2^2 + \dots +2^n = 2^{n+1} - 1 - 2^0 = 2^{n+1} - 2$

So, $a = 1, b = 1, c = 2$ (care for the negative sign in equation of question)