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