Solving recurrence $T(n) = T(n-2) +2 \log(n)$ using the Substitution Method

Question

$T(n) = T(n-2) +2 \log(n)$ if n>1 & 1 if n=1

So I start by substituting 3 times to get an idea about the pattern:

1. $T(n)=T(n-4) + 2 \log(n-2) + 2 \log n$

2. $T(n)=T(n-6) + 2\log(n-4) + 2\log(n-2) + 2\log n$

After k steps this will be:

3. $T(n)=T(n-2k) + 2\log(n-(2k-2)) + 2\log(n - (2k-4)) + \dots + 2\log n$

Now Since $T(1) = 1$, I put :

$$n-2k=1 \iff k = (n-1)/2$$

Which gives :

$$T(n) = T(1) + 2 (\log 3 + \log 5 + \log 7 + \log 9 + \dots + \log n)$$

I don't know how to solve this logarithmic series , I do know the answer is $O(n \log n)$ but how do we reach there can someone please help me here.

Answer 1

The sum of logs is approximated (very well) by the integral $\int_1^n \log x d x = x \log x - x.$

Answer 2

$T(n) = T(1) + 2 (\log 3 + \log 5 + \log 7 + \log 9 + \dots + \log n)$

$= T(1) + 2 (\log(3*5*....n))$

$= T(1) + 2 (\log(\frac{n!}{2*4....n}))$

$= T(1) + 2 (\log(\frac{n!}{2(1...\lfloor\frac{n}{2}\rfloor)}))$

$= T(1) + 2 (\log(\frac{n!}{2\lfloor\frac{n}{2}\rfloor!}))$

Answer 3

If the boundary value is $T_1 = 1$, you do keep getting $T_3 = 1+ 2 \log 3, T_5 = 1 + 2 \log 3 + 2 \log 5$ and so on, so the $n^{\text{th}}$ term will in fact be $T_n = 1 +2 \sum_{k=1}^{\frac{n-1}{2}}\log (2k+1)$, and yes, it doesn't exist in closed form, so you should approximate it with an integral (using Taylor series the integrand is $\log 2 + \log x +\frac{1}{2x}$)