1
$\begingroup$

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.

$\endgroup$
8
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I still reach a similar sum like the one I posted which I can't seem to figure out $\endgroup$ – Binyamin Pinnick Apr 25 '18 at 15:42
1
$\begingroup$

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})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.