I've got an recurrent function to solve.
$T_1 = 1$
$T_n = 2T_{\frac n2} + \frac{1}{2}n\log n$
I've got a tip to this excercise to determine additional variable as $k = 2^n$, where $ k = 1, 2, 3, ...$
But after some calulations I'm wondering if $k=2^n$ can i say that $2^{k-1} = n - 1$ ?
I recieve following equation: $T_{2^k} = 2T_{2^{k-1}} + 2^{k-1}k*\log2$ , am i correct? What can i do next?
We can prove by induction that $$T_n = 2^kT_{\frac{n}{2^k}} + \frac{k}{2}n\log(n)-\sum_{i=0}^{k-1}\frac{in}{2}$$ This clearly holds for the base case $k = 1$. So assuming it holds for some $k$, we find: \begin{align} T_n &= 2^kT_{\frac{n}{2^k}}+\frac{k}{2}n\log(n) - \sum_{i=0}^{k-1}\frac{in}{2}\\ &= 2^k\left(2T_{\frac{n}{2^{k+1}}} + \frac{1}{2}\frac{n}{2^k}\log\left(\frac{n}{2^k}\right)\right)+\frac{k}{2}n\log(n) - \sum_{i=0}^{k-1}\frac{in}{2}\\ &=2^{k+1}T_{\frac{n}{2^{k+1}}} + \frac{n}{2}\log(n) - \frac{n}{2}\log(2^k)+\frac{k}{2}n\log(n) - \sum_{i=0}^{k-1}\frac{in}{2}\\ &= 2^{k+1}T_{\frac{n}{2^{k+1}}}+\frac{k+1}{2}n\log(n)-\sum_{i=0}^{k}\frac{in}{2} \end{align} So we have the claim. The sum has an easy closed form, so we may rewrite $T_n$ as: $$T_n = 2^kT_{\frac{n}{2^k}}+\frac{k}{2}n\log(n)-\frac{k(k-1)}{4}n$$ Letting $k= \log(n)$, we have: \begin{align} T_n&=nT_1+\frac{n}{2}\log^2(n)-\frac{n}{4}\log(n)(\log(n) - 1)\\ &=n + \frac{n}{4}\log^2(n)+\frac{n}{4}\log(n) \end{align}