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?