find recurrence relation $T(n)=2T(n/2) +\log_2(n)$

Question

$$\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?

Answer 1

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?

Answer 2

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*}$$