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$
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$ Mar 3 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
    Mar 3 at 12:00
  • 2
    $\begingroup$ We can get better estimates via the Euler–Maclaurin formula. $\endgroup$ Mar 3 at 12:03
  • $\begingroup$ Thank you. Now that's clear ;) $\endgroup$
    – D. Caruso
    Mar 3 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, privacy policy and cookie policy

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