Question

Solve the recurrence relation T(n) = 2T(n / 2) + 3n where T(1) = 1 and k n = 2 for a nonnegative integer k. Your answer should be a precise function of n in closed form. An asymptotic answer is not acceptable. Justify your solution.

Answer 1

`Hey,

Note: If you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

given

t(n)=2*t(n/2)+3*n

So, by using back substitution

t(n)=2^2*t(n/2^2)+3*(n+2*n/2)=2^2*t(n/2^2)+3*2*(n)

..

..

t(n)=2^k*t(n/2^k)+3*k*n

So, base case n/2^k=1, k=log(n)

So,

t(n)=2^log(n)+3*n*log(n)=n+3*n*log(n) (Log properties)

So,

T(n)=n+3*n*log(n)

Kindly revert for any queries

Thanks.