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.

I was solving recurrence relation of Introduction to Algorithms by {Cormen, Leiserson, Rivest, Stein}, 3rd. edition. Problem 4-3 (i)
$$ T(n) = T(n-2) + \frac{1}{lg \; n} $$

I tried few ways, like expending with iteration method. With that i came up with the following equations - For even -

$$ T(n) = T(0) + \frac{1}{lg \; n} + \frac{1}{lg \; (n-2)} + \frac{1}{lg \; (n-4)} + ... + \frac{1}{lg \; 6} + \frac{1}{lg \; 4} + \frac{1}{lg \; 2} $$

For odd

$$ T(n) = T(1) + \frac{1}{lg \; n} + \frac{1}{lg \; (n-2)} + \frac{1}{lg \; (n-4)} + ... + \frac{1}{lg \; 7} + \frac{1}{lg \; 5} + \frac{1}{lg \; 3} $$

We can assume $T(1)=1$ and $T(0) = 1$. So to solve it I need to be able to sum up

$$ \sum ^{n}_{i=2} \frac{1}{lg\;i} $$

I was kinda lost, but got an idea from whuber from mathematica.stackexchange.com. We can view $1/lg(i)$ as the area of a rectangle of height $1/lg(i)$ and width $1$ centered at $i$, we have

$$\sum_{i=2}^n \frac{1}{lg(i)} \approx \int_{x=3/2}^{n+1/2} \frac{dx}{lg(x)}.$$

But that didn't help much in terms of typical asymptotic analysis. Some help will be greatly appreciated. Thanks.

share|improve this question
1  
What should you do with it? Give an explicit form? Maybe you need this one: en.wikipedia.org/wiki/Master_theorem –  Berci Oct 3 '12 at 17:50

1 Answer 1

Note that $$\int_a^b \dfrac{dx}{\ln x} = \int_0^{b-a} \dfrac{dt}{\ln(b-t)} = \int_0^{b-a} \dfrac{dt}{\ln(b) + \ln(1-t/b)} = \int_0^{b-a} \dfrac{dt}{\ln(b) - t/b + \ldots}$$ $$ = \int_0^{b-a} \left( \frac{1}{\ln(b)} + \frac{t}{b \ln(b)^2} + \ldots\right)\ dt$$

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.