What is the bound of :   $ T(n)=T(n-2)+\log(n)$? Given : $T(n)=T(n-2)+\log(n)$
I need to find the bound for the above recurrence . 
So:
$$\begin{align*}
T(n-2)&=T(n-2-2)+\log(n-2)\\
&=T(n-4)+\log(n-2)\\
T(n)&=T(n-2)+\log(n)\\
&=T(n-4)+\log(n-2)+\log(n)\\
T(n-4)&=T((n-4)-2)+\log(n-4)\\
T(n)&=T(n-4)+\log(n-2)+\log(n)\\
&=T(n-6)+\log(n-4)+\log(n-2)+\log(n)\\
&\vdots\\
T(n)&=\Theta(2)+\sum_{i=1}^n\log(2i)\\ 
    &=\Theta(2)+\log\left(\Pi_{i=1}^n2i\right)\\
    &=\Theta(2)+\log((2i)!)\\
    &=\Theta(n\log(n))
\end{align*}$$
Is this correct ? 
Regards
 A: You’ve made a couple of mistakes: you’ve implicitly assumed that $n$ is even, and you’ve miscounted the steps needed to reduce $T(n)$.
If $n=2m$, your calculation, with the errors fixed, shows that $$T(n)=T(0)+\sum_{k=1}^m\log 2k\;;$$ if $n=2m+1$, it shows that $$T(n)=T(1)+\sum_{k=1}^m\log(2k+1)\;.$$
In each case the summation has $\lfloor n/2\rfloor$ terms, each of which is at most $\log n$, so $$T(n)\le\max\{T(0),T(1)\}+\frac{n}2\log n\;;$$ this clearly implies that $T(n)$ is $O(n\log n)$.
If you want to look closer, you can work out that $$\sum_{k=1}^n\log 2k=\log\prod_{k=1}^m 2k=\log 2^mm!\;,$$ and 
$$\begin{align*}
\sum_{k=1}^m\log(2k+1)&=\log\prod_{k=1}^m(2k+1)\\
&=\log\Big(3\cdot5\cdot \ldots\cdot(2m+1)\Big)\\
&=\log\frac{(2m+1)!}{2\cdot4\cdot\ldots\cdot(2m)}\\
&=\log\frac{(2m+1)!}{2^mm!}\;,
\end{align*}$$
but these aren’t easily going to give you nice bounds better than the one that you already have. A better idea, if you need more precise information, is to note that the sums of logs can be approximated by integrals over appropriate limits of the function $f(x)=\log 2x$.
A: The sum $\log(n) + \log(n-2) + \dots $ has at most $n/2$ terms with each term $\leq \log(n)$.  This leads to an upper bound of $(n/2)\log(n)$.  To understand the more precise asymptotics of $T(n)$ the sum of logarithms can be compared geometrically and algebraically to $\int_0^{(n-1)/2} \log (n-2x) dx$.
The derivation in the question is correct for even $n$, with a similar argument valid for odd $n$, assuming that $\log n! = O(n \log n)$ is known.  Using Stirling's approximation, very precise estimates of $T(2k)$ and $T(2k+1)$ can be made that go beyond the step-function or trapezoidal approximations to the integral.
A: I think that because we have $\frac n2$ terms, so the answer would be $\frac n2 \cdot \log(n)$ and so on the answer would be $O(n\log(n))$.
