Sign up ×
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.

This question already has an answer here:

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

marked as duplicate by Daniel Fischer Feb 21 at 21:57

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new 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|cite|improve this answer
Might want to check those small values of $i$ in your sums... – Erick Wong Sep 12 '12 at 4:48

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