6
$\begingroup$

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

  • 0
    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!2012-04-04

3 Answers 3

4

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

  • 0
    @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.2012-04-04
3

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.

0

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