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

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$ – user2468 Apr 4 '12 at 5:50
4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – zyx Apr 4 '12 at 6:27
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Apr 4 '12 at 6:31
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.