Proving the recurrence $T(n) = T(n-2) + 2\log(n)$ is $\Theta(n*\log n))$

Question

What I had in mind was to show, I know for $T(n) = T(n-1) + \ln(n)$, I can write it as $\sum_{i=0}^{n-1}\log(n-i)$ which is essentially $\log(\prod_{i=1}^{n}n) \to \log(n!)$. And knowing $\log(n!) \in \Theta(n\log n)$, I thought my initial recurrence would be upper-bounded by this thus is $O(n\log n)$. But I am not able to fully convince myself of this nor am I able to show that it is also $\Omega(n\log n)$. Some pointers would be really great.

Answer 1

Not sure why this is not the same. Assuming $n = 2k$ is even, you get $$ \begin{split} T(2k) &= T(2k-2) + 2\log(2k) \\ &= T(2k-4) + 2\log(2k-2) + 2\log(2k) \\ & \ldots\\ &= T(2k-2k) + 2\sum_{i=1}^k \log(2i) \\ &= T(0) + 2\log\left( \prod_{i=1}^k 2i \right) \\ &= T(0) + 2\log\left( 2^k k! \right) \\ &= T(0) + 2k + 2\log(k!) \end{split} $$ can you finish this now?

UPDATE

From your questions on odd $n$, assume $n=2k+1$ is odd to get $$ \begin{split} T(1+2k) &= T(1+2k-2) + 2\log(1+2k) \\ &= T(1+2k-4) + 2\log(1+2k-2) + 2\log(1+2k) \\ & \ldots\\ &= T(1+2k-2k) + 2\sum_{i=1}^k \log(1+2i) \\ &= T(1) + 2\log\left( \prod_{i=1}^k (1+2i) \right) \\ &= T(1) + 2\log\left( \frac{n!}{\prod_{i=1}^k (2i)} \right) \\ \end{split} $$ and the denominator sum can be handled as in the even case...

Answer 2

If I gave you the recurrence relation $T(n)=aT(n-2)$, you would realize that (a) this is a $2^{nd}$-order recurrence that requires two initial conditions, e.g., $T(1)$ and $T(2)$, and (b) that the solutions for odd and even $n$ separate as follows (e.g., by induction)

$$ T(n_{odd})=T(1)a^{n-1}\\ T(n_{even})=T(2)a^n\\ $$

The present inhomogeneous recurrence must be treated similarly. Thus, I find by induction that

$$ T(n_{odd})=T(1)+c\log\prod_{j=1}^{(n-1)/2}(2j+1)\\ T(n_{even})=T(2)+c\log\prod_{j=2}^{n/2}2j\\ $$

For your problem, of course, $c=2$. Now, this might be expressed more succinctly with double factorials, but I don' have those in my programming language anyway, so I didn't bother. I have verified this solution with the recurrence relation for random real and complex values for all parameters $[T(1,2), c]$.