Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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