2
$\begingroup$

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.

  • 1
    What should you do with it? Give an explicit form? Maybe you need this one: http://en.wikipedia.org/wiki/Master_theorem2012-10-03

1 Answers 1

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$