Solve the Recurrence : $T(n) = 2T(\frac{n}{2}) + n + \log n$

Question

I have tried Akra-Bazzi, which gave me O(n logn), but I am unsure if that can be applied here, or even if it can be applied, if my final answer is correct or not. How can I try solving this?

Answer 1

I assume you're only interested in finding an asymptotics for $T$ and not an explicit formula.

• First consider the case $n=2^p$, and set $S(p)=T(2^p)$.

Then $S(p) - 2S(p-1) =2^p +p\log(2)$.

This is a linear recurrence. So the general solution has the form "homogeneous + particular".

$$S(p)-2^{p}S(0)=\sum_{k=1}^{p}2^{p-k}(S(k)-2S(k-1))=\sum_{k=1}^p 2^{p-k}(2^k+k\log(2))=p2^p+2^p\log(2)\sum_{k=1}^{p}\frac{k}{2^k}$$

Now $$\begin{equation}\begin{split}\sum_{k=1}^{p}\frac{k}{2^k}&=2\sum_{k=1}^{p}\frac{k}{2^k}-\sum_{k=1}^{p}\frac{k}{2^k} &=\sum_{k=1}^{p}\frac{k}{2^{k-1}}-\sum_{k=1}^{p}\frac{k}{2^k}\\ &=\sum_{k=0}^{p-1}\frac{k+1}{2^k}-\sum_{k=1}^{p}\frac{k}{2^k} &=\sum_{k=0}^{p-1}\frac{1}{2^k}-\frac{p}{2^p}\\ &=2-2^{1-p}-p2^{-p}&=2+(-2-p)2^{-p} \end{split}\end{equation}$$

Going back, $$S(p)-2^{p}S(0)=p2^p+(2^{p+1}+(-2-p))\log(2)$$

In particular, there exists $c>0$ such that for $p$ large enough, $$p2^p\le S(p) \le cp2^p$$

• General case. Since $T$ is increasing, and $2^p \le n < 2^{p+1}$ where $p=\lfloor \log_2(n)\rfloor$, we have $$S(p)\le T(n)\le S(p+1)$$

And in particular, $p2^p\le T(n)\le c(p+1)2^{p+1}$ so that $$T(n)=O(\log(n)n)$$