2
$\begingroup$

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?

$\endgroup$

2 Answers 2

3
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ In fact, $\log\log(n+1)-\log\log n$ is decreasing, since $(\log \log x)' = 1/x\log x$ is decreasing. You can check it for concrete values of $n$ $\endgroup$ Commented Mar 3, 2021 at 11:59
  • 1
    $\begingroup$ Because T(n) - T(2) is between the two integrals, the integral from 2.5 to n + 0.5 is probably a better approximation. $\endgroup$
    – gnasher729
    Commented Mar 3, 2021 at 12:00
  • 2
    $\begingroup$ We can get better estimates via the Euler–Maclaurin formula. $\endgroup$ Commented Mar 3, 2021 at 12:03
  • $\begingroup$ Thank you. Now that's clear ;) $\endgroup$
    – D. Caruso
    Commented Mar 3, 2021 at 12:25
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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