# 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

-
I tried Akra-Bazzi, and I got $$\Theta(1 + \int_1^{n} \frac{\log(x)}{x}\, dx) = \Theta(\log^2 n).$$ May be I made a mistake! – user2468 Apr 4 '12 at 5:50

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

-
Stirling's formula (including the $\sqrt{2 \pi}$ factor) gives asymptotics for $T(n)$ with $o(1)$ accuracy, if the even and odd values of $n$ are considered separately. – zyx Apr 4 '12 at 6:27
@zyx: True enough; don’t know why I didn’t think of that. Thanks. I don’t think that I’ll bother, though, as I suspect that that’s more than the OP needs; I went as far as I did mostly to give the OP a taste of the kinds of manipulations that are possible. – Brian M. Scott Apr 4 '12 at 6:31

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.

-

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))$.

-