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.

-
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

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