find recurrence relation $T(n)=2T(n/2) +\log_2(n)$ $$\begin{align*}
&T(n) = 2T(n/2) + \log_2(n)\\
&T(1) = 0  
\end{align*}$$
$n$ is a power of $2$
solve the recurrence relation 
my work so far:
unrolling this, we have
$$\begin{align*}
T(n) &= 4T(n/4) + \log_2(n) -1\\
&= 8T(n/8) + 2\log_2(n) -2\\
&=\log_2(n-1) \log_2(n) - \log_2(n) + 1
\end{align*}$$
after substituting for base case.
where is my mistake?
 A: You didn’t perform the unrolling correctly.
I will write $\lg n$ for $\log_2 n$. Suppose that $n=2^m$; then
$$\begin{align*}
T(n)&=T(2^m)\\
&=2T(2^{m-1})+\lg 2^m\\
&=2T(2^{m-1})+m\\
&=2\Big(2T(2^{m-2})+\lg 2^{m-1}\Big)+m\\
&=2^2T(2^{m-2}+2(m-1)+m\\
&=2^2\Big(2T(2^{m-3})+\lg 2^{m-2}\Big)+2(m-1)+m\\
&=2^3T(2^{m-3})+2^2(m-2)+2(m-1)+m\\
&\;\vdots\\
&=2^kT(2^{m-k})+\sum_{i=0}^{k-1}2^i(m-i)\\
&\;\vdots\\
&=2^{m-1}T(1)+\sum_{i=0}^{m-2}2^i(m-i)\\
&=\sum_{i=0}^{m-2}2^i(m-i)\\
&=m\sum_{i=0}^{m-2}2^i-\sum_{i=0}^{m-2}i2^i\;.
\end{align*}$$
Can you finish it by evaluating those two summations to get a closed form?
A: Substituting $n=2^k$ we have:
$$\begin{align*}T(n)=T(2^k)&=2T(2^{k-1})+k=2(2T(2^{k-2})+k-1)+k=4T(2^{k-2})+3k-1\\
&=4(2T(2^{k-3})+k-3)+3k-1=8T(2^{k-3})+7k-13=...=\\
&= 2^mT(2^{k-m})+\sum_{t=1}^m2^{t-1}(k-t+1)=...=2^kT(1)+\sum_{t=0}^{k-1}2^t(k-t)\\
&=2^k\cdot0+k\sum_{t=0}^{k-1}2^t-\sum_{t=0}^{k-1}t2^t=k\frac{2^k-1}{2-1}-2\frac{(k-1)2^k-k2^{k-1}+1}{2-1}\\
&=k2^k-k-2(k-1)2^k+k2^k-2=2k2^k-2k2^k+2\cdot2^k-k-2=\\
=&2\cdot2^k-k-2=2n-\log_2n-2\end{align*}$$
