# How can i solve the recurrence $T(n)=2T(n-2)+n\log n$

What would be the solution of the following recurrence? $$T(n) = 2T(n-2) + n\log n.$$

I've managed to get:

$$T(n) = 2^{n/2}T(0)+\sum_{i=0}^{n/2} 2^i (n-2i) \log(n-2i).$$

The sum cannot be easily bounded for estimating the recurrence, because part of it increases while the other part decreases as the index grows.

Hint:

Let $n=2m$.

$$T(2m)=2T(2m-2)+2m\log(2m)$$

or

$$T'(m)=2T'(m-1)+2m\log(2m)$$

which has the classical form.

• I still reach a similar sum like the one I posted which I can't seem to figure out Apr 25 '18 at 15:42

Let $S(m) = T(2m)/2^m$. Then $$S(m) = \frac{T(2m)}{2^m} = \frac{2T(2m-2) + (2m)\log(2m)}{2^m} = S(m-1) + \frac{m\log(2m)}{2^{m-1}}.$$ It follows that $$S(m) = S(0) + \sum_{t=1}^m \frac{t\log(2t)}{2^{t-1}}.$$ If we extend the sum on the right to infinity, then we get a convergent series. In other words, $S(m) = \Theta(1)$, and so $T(n) = \Theta(2^{n/2})$.