# How to solve the recurrence $T(n) = \frac{n}{2}T(\frac{n}{2}) + \log n$

I am trying to solve the recurrence below but I find myself stuck.

$T(n) = \frac{n}{2}T(\frac{n}{2}) + \log n$

I have tried coming up with a guess by drawing a recurrence tree. What I have found is

number of nodes at a level: $\frac{n}{2^{i}}$
running time at each node: $\log \frac{n}{2^{i}}$
total running time at each level: $\frac{n}{2^{i}} \log \frac{n}{2^{i}}$

I try to sum this over through n > $\log n$ which is the height of the tree

\begin{align} \sum\limits_{i=0}^n \frac{n}{2^{i}} \log \frac{n}{2^{i}}&= n \sum\limits_{i=0}^n \frac{1}{2^{i}} \log \frac{n}{2^{i}}\\ &=n \sum\limits_{i=0}^n \frac{1}{2^{i}} (\log n - \log 2^{i})\\ &=n \sum\limits_{i=0}^n \frac{1}{2^{i}} \log n - \sum\limits_{i=0}^n \frac{1}{2^{i}} \log 2^{i}\\ &=n \sum\limits_{i=0}^n \frac{1}{2^{i}} \log n - \sum\limits_{i=0}^n \frac{ \log 2^{i}}{2^{i}}\\ &=n \sum\limits_{i=0}^n \frac{1}{2^{i}} \log n - d \sum\limits_{i=0}^n \frac{i}{2^{i}}\\ &=2 n \log n - d \sum\limits_{i=0}^n \frac{i}{2^{i}} \end{align}

I am still trying to figure out the sum of the second summation above but I somehow feel that it will be bigger than $2n \log n$ which makes my whole approach wrong.

Is there another way to tackle this problem?

-
What if $n$ is odd? And what is $T(1)$? – TonyK Jan 25 '12 at 11:30

Consider the equality $$1+x+x^2+...+x^n=\frac{x^{n + 1} -1}{x-1}$$ Differentiate it by $x$, then multiply by $x$: $$x+2x^2+3x^3+...+n x^n=\frac{nx^{n+2} - (n + 1)x^{n+1} + x}{(x-1)^2}$$ Now we can substitute $x=\frac{1}{2}$ and obtain $$\sum\limits_{i=0}^n\frac{i}{2^i}=n\left(\frac{1}{2}\right)^{n} - (n + 1)\left(\frac{1}{2}\right)^{n-1} + 2$$

-

The summation $$\sum\limits_{i=0}^n \frac{i}{2^{i}}$$

is equal to $$\sum\limits_{i=0}^n i(\frac{1}{2})^i$$

which is of the form $$\sum\limits_{i=0}^n ix^i, x = \frac{1}{2}$$

Consider the summation $$\sum\limits_{i=0}^n x^i = \frac{x^{n+1} - 1}{x - 1}$$

By differentiating with respect to $x$ we have $$\frac{d}{dx}\left( \sum\limits_{i=0}^n x^i \right) = \frac{d}{dx} \left( \frac{x^{n+1} - 1}{x - 1} \right)$$ $$\Rightarrow \sum\limits_{i=0}^n ix^{i-1} = \frac{(x - 1)(n + 1)x^n - (x^{n+1} -1)(1)}{(x - 1)^2}$$ $$\Rightarrow \sum\limits_{i=0}^n ix^{i-1} = \frac{(x^{n+1} - x^n)(n + 1) - x^{n+1} + 1}{(x - 1)^2}$$ $$\Rightarrow \sum\limits_{i=0}^n ix^{i-1} = \frac{(nx^{n+1} - nx^n) + (x^{n+1} - x^n) - x^{n+1} + 1}{(x - 1)^2}$$ $$\Rightarrow \sum\limits_{i=0}^n ix^{i-1} = \frac{nx^{n+1} - nx^n + x^{n+1} - x^n - x^{n+1} + 1}{(x - 1)^2}$$ $$\Rightarrow \sum\limits_{i=0}^n ix^{i-1} = \frac{nx^{n+1} - nx^n - x^n + 1}{(x - 1)^2}$$ By multiplying $x$ to both sides, $$x\sum\limits_{i=0}^n ix^{i-1} = x\left( \frac{nx^{n+1} - nx^n - x^n + 1}{(x - 1)^2} \right)$$ $$\Rightarrow \sum\limits_{i=0}^n ix^{i} = \frac{nx^{n+2} - nx^{n+1} - x^{n+1} + x}{(x - 1)^2}$$ By substitution $\left( x = \frac{1}{2} \right)$, $$\sum\limits_{i=0}^n i\left(\frac{1}{2}\right)^{i} = \frac{n\left(\frac{1}{2}\right)^{n+2} - n\left(\frac{1}{2}\right)^{n+1} - \left(\frac{1}{2}\right)^{n+1} + \left(\frac{1}{2}\right)}{(\left(\frac{1}{2}\right) - 1)^2}$$

$$\Rightarrow \sum\limits_{i=0}^n i\left(\frac{1}{2}\right)^{i} = \frac{n\left(\frac{1}{2^{n+2}}\right) - n\left(\frac{1}{2^{n+1}}\right) - \left(\frac{1}{2^{n+1}}\right) + \left(\frac{1}{2}\right)}{\left(-\frac{1}{2}\right)^2}$$

$$\Rightarrow \sum\limits_{i=0}^n i\left(\frac{1}{2}\right)^{i} = \frac{\frac{n}{2^{n+2}} - \frac{n + 1}{2^{n+1}} + \frac{1}{2}}{\left(\frac{1}{4}\right)}$$

$$\Rightarrow \sum\limits_{i=0}^n i\left(\frac{1}{2}\right)^{i} = 4 \left( \frac{n}{2^{n+2}} - \frac{n + 1}{2^{n+1}} + \frac{1}{2} \right)$$

$$\Rightarrow \sum\limits_{i=0}^n i\left(\frac{1}{2}\right)^{i} = 4 \left( \frac{n}{2^{n+2}} - \frac{2(n + 1)}{2^{n+2}} + \frac{2^{n+1}}{2^{n+2}} \right)$$

$$\Rightarrow \sum\limits_{i=0}^n i\left(\frac{1}{2}\right)^{i} = \frac{n - 2(n + 1) + 2^{(n+1)}}{2^{n}}$$

$$\Rightarrow \sum\limits_{i=0}^n \frac{i}{2^{i}} = \frac{n - 2(n + 1) + 2^{(n+1)}}{2^{n}}$$

-

Summary: Like in several questions of the same ilk asked previously on the site, the recursion can only determine each $T(n)$ as a function of $T(2i+1)$ and $k\geqslant0$, where $n=(2i+1)2^k$. Furthermoree, the series considered by the OP are simply not relevant to the asymptotics of $T(n)$. The growth of $T(n)$ of the order of $n\log n$, which the OP seems to infer, is not compatible with the recursion at hand since, speaking very roughly, $T(n)$ grows like $n^{\frac12\log n}$.

Gory details: Consider for example $t_k=T(2^k)$. Then, for every $k\geqslant1$, $$t_k=2^{k-1}t_{k-1}+k\log2,$$ hence the change of variables $s_k=2^{-k(k-1)/2}t_k$ yields the recursion $s_0=t_0=T(1)$ and $s_k=s_{k-1}+2^{-k(k-1)/2}k\log2$. This is solved by $$s_k=s_0+\log2\sum\limits_{i=1}^ki2^{-i(i-1)/2},$$ whose translation in terms of $t_k$ is $$t_k=2^{k(k-1)/2}\left(T(1)+\log2\sum\limits_{i=1}^k\frac{i}{2^{i(i-1)/2}}\right).$$ Finally, $$T(2^k)=2^{k(k-1)/2}\tau_0-(\log2)\,(k/2^{k})+o(k/2^k),$$ with $$\tau_0=T(1)+(\log2)\,\sum\limits_{i=1}^{\infty}\frac{i}{2^{i(i-1)/2}}= T(1)+1.69306\ldots$$ Conclusion: One sees that, along the subsequence indexed by the powers of $2$, $T(n)$ grows roughly like $n^{\frac12\log n}$ rather than like $n\log n$. The same argument applies to each subsequence indexed by the powers of $2$ times any given odd integer.

-