Solving a recurrence for T(n)
I need to Find the solution of the recurrence for n, a power of two if
T(n)=3T(n/2)+n for n>1 and T(n)=1 otherwise.
using substitution of n=2^m,S(m)=T(2^(m-1)) I can get down to:
S(m)=2^m+3*2^(m-1)+3^2*2^(m-2)+⋯+3^(m-1) 2^1+3^m
But I have no idea how to simply that. Any help is appreciated!1
No comments:
Post a Comment