How to solve $T(n)= T(n - 1) + \frac{1}{n\log n}$?

Question

I am interested in the asymptotic bounds of the following recurrence:

$$T(n)= T(n - 1) + \frac{1}{n\log n}$$

with base case $T(1) = 1$. I'm having trouble while solving this recurrence. It seems much more tricky than I initially thought.

I've tried out by iterative method and since $\log(n!) = n\log n$, I've got $\frac{1}{n\log n}$.

At this point, I've got that the summation of $\frac{1}{i}$ is equal to $\Theta(\log n + O(1))$. So at the end, I've come up with this bound (by simplifying the two terms): $\Theta(\frac{1}{n})$.

I'm not so sure about this bound. What is a good way to approach this problem?

Answer 1

We have $$ T(n) = \sum_{m=3}^n \frac{1}{m\log m} + T(2). $$ We can bound $$ \int_3^{n+1} \frac{dx}{x\log x} \leq \sum_{m=3}^n \frac{1}{m\log m} \leq \int_2^n \frac{dx}{x\log x}. $$ Since $(\log\log x)' = \frac{1}{x\log x}$, this shows that $$ \log\log(n+1) - \log\log 3 \leq \sum_{m=3}^n \frac{1}{m\log m} \leq \log\log n - \log\log 2, $$ and so $T(n) = \log\log n + \Theta(1)$.

Answer 2

First, this isn’t a recursion, it’s just a straightforward sum, adding 1 / (j log j) for j = 2 to n, plus 1 added.

Remember how the sum of 1/j is about log (n)? You are adding something similar, but smaller. Find an upper and lower bound for the sum from 2 to 2, from 3 to 4, from 5 to 8, from 9 to 16, from 17 to 32 etc. and use that to get T(2^k), and then it is easy.

I’d bet the result is about log log n. Take the derivative: (log log n)’ = log’ (log n) * (log n)’ = (1 / log n) * (1 / n). Just right. Now T(n) - T(n-1) would usually be closer to f’(n-1/2), so I’d say T(n) ≈ c + log(log(n-1/2)), picking c so that the error is small for large n.