$T(n) = T(n-2) + log n$ Does anyone know how to solve this example?
I start with this :
$T(n) = T(n-2) + \log n$
$T(n-2) = T(n-4) + \log(n-2)$
$T(n-4) = T(n-6) + \log (n-4)$
Now i substitute back:
$T(n-2) = T(n-6) + \log(n-4) + \log(n-2)$
$T(n) = T(n-6) + \log(n-4) + \log(n-2) + \log n$
Now i see a pattern here so i substitute it again:
$T(n) = T(n-2\times k) +$ $\sum\nolimits_{k=2}^n$ $(\log 2\times k)$
then $n-2\times k = 1 \implies k = \frac{n-1}{2}$
Now i am stuck with this term:
$T(n) = T(1) +$ $\sum\nolimits_{k=2}^n$ $\log 2\times \frac{n-1}{2}$
How shall I go on?
 A: The correct recursion for even terms would be
$$T(2n) = T(2n-2) + \log(2n) = T(2n-2k) + \sum_{j=0}^{k-1}\log(2n-2j) $$
Substituting $k=n$ gives
\begin{align}
T(2n) &= T(0) + \sum_{j=0}^{n-1}\left[\log(2) + \log(n-j)\right]\\
&= T(0) + \log(2)\cdot n + \sum_{j=0}^{n-1} \log(n-j)\\
&= T(0) + \log(2)\cdot n + \log\left(\prod_{j=0}^{n-1} (n - j)\right)\\
&=  T(0) + \log(2)\cdot n + \log(n!)\\
&\overset{\text{Stirling's}}{\sim} T(0) + \log(2)\cdot n + \ln\left(\sqrt{2\pi n}\left(\frac{n}{e}\right)^n \right)
\in \Theta(n\log n)
\end{align}
For odd terms we ultimately find
\begin{align}
T(2n+1) &= T(1) + \sum_{j=0}^{n-1} \log(2n - 2j -1)\\
&= T(1) + \log\left(\prod_{j=0}^{n-1} (2n-2j-1)\right)
\end{align}
The product is just $$(1)\cdot (3)\cdot \dotsb\cdot(2n-1)$$
that we can deal with by writing it in terms of factorials:
\begin{align}(1)\cdot (3)\cdot \dotsb\cdot(2n-1) &= \frac{(1)(2)(3)(4)\dotsb(2n-1)(2n)}{(2)(4)\dotsb (2n)}\\
&= \frac{(1)(2)(3)(4)\dotsb(2n-1)(2n)}{(1)(2)\dotsb (n) 2^n}
= \frac{(2n)!}{n! 2^n} \end{align}
So using Stirling's again:
\begin{align}
T(2n-1) &= T(1) + \log \frac{(2n)!}{n!2^n}\\
&\sim T(1) + \log  \frac{\sqrt{2\pi \cdot(2n)}\left(\frac{(2n)}{e}\right)^{(2n)} }{\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n} 2^n}\\
&= T(1) + \log\left(\sqrt{2}\cdot 2^{2n-1} n^{2n} e^{-n}\right)\\
&\sim \log(n^{2n}) = 2n \log (n) \in \Theta(n\log n)
\end{align}
Therefore $T(n)$ is $\Theta(n \log n)$.
Alternatively If we look at the computation of area under $\log(2x)$, we may approximate the sum of logs:
$$\int_1^n \log(2x)\;dx
\leq \sum_{k=1}^n \log\big(2(k+1)\big)
 \leq \int_2^{n+1} \log(2x)\;dx$$
given that $\int \log(2x) \;dx = x\left[\log(2x) - 1\right] + C$, we find that both the upper and lower bound are $\Theta\big( n\log (n) \big)$. Hence
$$ \sum_{k=1}^n \log\big(2(k+1)\big) = T(2n) - T(0) + \log(2n+2) \in \Theta\big( n\log (n) \big)$$ so $T(2n) \in \Theta\big( n\log (n) \big)$.
A near identical argument for $T(2n+1)$ shows the same thing.
