What is the bound of : $ T(n)=T(n-2)+\log(n)$?

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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