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?
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.