Question

Solve the recurrence using change of variable method: T(n) = 2T(n/2)+nlogn

Answer 1

Let be $n=2^m$ therefore n/2=$2^{m-1}$ and we have

$T(2^m)=2T(2^{m-1})+m2^m$

Let S(m)=$T(2^m)$ , then $S(m)=2S(m-1)+m2^m$

Let we prove by induction that S(m)$\le c\cdot m^2\cdot 2^m$ ;

Assume it is true for k<m,then

$S(m) \le 2c(m-1)^2\cdot 2^{m-1}+m\cdot {2^m}=2^m\cdot c\cdot (m^2+1-2m+\frac{m}{c}))\le m^2 \cdot 2^m$

if c>1. Base of induction will be fulfilled if C would be taken as S(1)$\le 2c,c\ge 1$

It s always possble.

Now we return to variable n=log(m) and have $T(n)\le c\cdot n\cdot (log( n))^2$

This is upper bound of increasing means $T(n)=O\left(n\cdot (log( n))^2\right)$ this is solution og given reccurence.