386 views
0 votes
0 votes

T(n)=2T(n-1)+n-1, T(1)=1 , n>=2


T(n)=2kT(n-k)+2(k-1)(n-(k-1))+2(k-2)(n-(k-2))+.......+n

Now k=n-1

T(n)=2(n-1)(1)+2(n-2)(2)+2(n-3)(3)+.......+2(n-n)(n)

T(n)=2(n)[ 1/1 + 2/2(2) +3/2 (3) + 2/ 2(4) +....]  + n

Now I am struck at this point how to proceed from here ?

Please log in or register to answer this question.

Related questions

1 votes
1 votes
0 answers
3
1 votes
1 votes
1 answer
4
iarnav asked Jul 29, 2017
2,502 views
Given RR as -T(n) = 2T(n/2)+n ; n>1T(1) = 1Solve this using only BACK SUBSTITUTION method? Note - I am stuck at T(n)= 2^k.T(n/2^k)+(2^k-1).nand I'm putting 2^k=n Please h...