I'm trying to solve this recurrence: $T(n) =T(n-2) + 1/\ln n$. And I can't make progress on.
What I did so far:
$$ \frac{1}{\ln(n - 2i)} = 1 \\ \ln(n-2i) = 1 \\ n - 2i = 2 \\ i = \frac{n-2}{2} $$
$ n' = i $, that is, n' is the tree's height.
$$ \sum_{i=0}^{n'} \frac{1}{\ln(n-2i)} \\ \sum_{i=1}^{n'+1} \frac{1}{\ln(2i)} $$
So, I'm stuck in here. Looks like that the correct answer is $ \theta(\ln(\ln(n)) $ by using the harmonic series, but I don't know how to get there.
$$T(n) = T(n - 2) + \frac {1}{\ln n}$$
So $$T(n) = \sum_{k}^{n/2} \frac{1}{\ln(2k)}$$
which will have the same asymptotic behavior as:
$$\begin{align} T(n) &\approx \int^{n/2} \frac{1}{\ln(2k)} ~{\rm d}k\\ &= -\frac 12 \Gamma(0, -\ln(n))/2 \\ &= \frac 12 E_1(\ln(n)) \end{align}$$
Where $\Gamma(,)$ is the incomplete gamma function and $E_1()$ is the Exponential integral. So bounds can be established with
$$\frac{1}{2}e^{-x}\,\ln\!\left( 1+\frac{2}{x} \right) < \mathrm{E_1}(x) < e^{-x}\,\ln\!\left( 1+\frac{1}{x} \right) \qquad x>0 $$
