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.

Trying to determine asymptotic of

$$T(n) = T(n-2) + \displaystyle\frac{1}{ \lg n}$$ $$\lg n = \log_{2}n $$

Last term $\frac{1}{ \lg n}$ give me a lot of trouble. Iterative method doesn't work. Tried change of variables, there is nothing to change.

share|improve this question
What is the $\lg$ function? Natural logarithm? –  Rod Carvalho Sep 12 '12 at 4:25
@RodCarvalho It is log base 2 (binary log) –  newprint Sep 12 '12 at 4:33
@newprint You should accept the answer that you find most useful. You have not accepted answers to any of your questions so far, even though they seem like good answers. –  Paresh Feb 9 '13 at 17:17

1 Answer 1

up vote 1 down vote accepted

Hint: You can bound $T(n)$ between $\frac 12 \sum_{i=4}^n \frac 1{\lg i}$ and $\frac 12 \sum_{i=4}^n \frac 1{\lg (i-2)}$ (to within a small correction), each of which is close to the logarithmic integral $\int \frac 1{\ln x}\; dx$, which goes as $\frac x{ \ln x}$ (like yours to within factors of $\ln 2$)

share|improve this answer
Might want to check those small values of $i$ in your sums... –  Erick Wong Sep 12 '12 at 4:48

Your Answer


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.