Time complexity of $T(n)= 2T(n-1) + \log n$

Question

I am trying to find the time complexity of the function given by equation $$T(n)= 2T(n-1) + \log n \text.$$ After the all the substitutions, I got the equation: $$T(n)=\log⁡ n + 2\log⁡(n-1) + 2^2 \log⁡(n-2) + 2^3 \log⁡(n-3) +\dots+ 2^{n-2} \log⁡ 2$$ $$T(n) = \sum_{i=0}^{n-2} 2^i \log(n-i)$$

How do I continue on to prove $T(n) = O(2^n \log n)$?

Answer 1

$T(n)=2^n \sum ( 2^{i-n} (\log n +\log(1-\frac{i}{n}))< 2^n \sum ( 2^{i-n}(\log n))= 2^{n} \log n \sum 2^{i-n}<2\cdot 2^{n} \log n$

so it is $O(2^n \log n)$.

On the other hand, I don't think this is the best bound.

$\sum 2^{i-n}\log (n-i)=\sum_2^n 2^{-x}\log x<\sum_2^\infty 2^{-x}\log x< \sum 2^{-x/2}2^{-x/2}\log x<C+\sum 2^{-x/2}<K$

So $T(n)$ is $O(2^n)$, and, in fact, $\Theta(2^n)$.