485 views

1 Answer

Best answer
6 votes
6 votes

$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)

selected by

Related questions

1 votes
1 votes
0 answers
1
syncronizing asked Mar 15, 2019
1,252 views
Is this the correct way to solve ?Q) int algorithm(int n){ int sum =0;k,j; for (k=0;k<n/2;k++) for(j=0;j<10;j++) sum++; return 4*algorithm(n/2)*algorit...
1 votes
1 votes
1 answer
2
VikramRB asked Jan 20, 2019
1,005 views
What is the time complexity of the following recurrence relation and step to derive the same$T(n) = T(\sqrt{n}) + log(logn)$
0 votes
0 votes
0 answers
4
garvit_vijai asked Nov 17, 2018
449 views
How to solve the following recurrence relation?T(n) = T(n-6) + n2 , n>7T(n) = 1 , n<= 7