find the asymptotic bound of $T(n-1) + n/\log n$

Question

As the title says: The question is to find the strict bound of $T(n)$: $$T(n) = T(n-1) + \frac{n}{\log n}$$ I used iteration and got this far $$T(n) = T(n-1) + \frac{n}{\log n} = T(n-2) + \frac{n-1}{\log(n-1)} + \frac{n}{\log n} = ...=T(1) + \sum_{i=2}^n \frac{i}{\log i}$$ Tried to bound it from both sides to no avail. Managed to do so with $$\sum_{i=2}^n \frac{i}{\log i} < \sum_{i=2}^n \frac{n}{\log n}= (n-1)\cdot\frac{n}{\log n} = O(n^2)$$ but didn't manage to find anything as lower bound with the same asymptotic relation to use the sandwitch rule. On the other hand I have managed to find the lower bound as with $$\sum_{i=2}^n \frac{i}{\log i}> \sum_{i=2}^n \frac{2}{\log 2} = (n-1)\cdot\frac{2}{\log 2} = O(n)$$ but not the corresponding upper bound. I have yet to learn integrals. Any help would be appreciated.

Answer 1

One way to get a stronger lower bound without integrating is a variant of the method you already used: $$ \sum_{i=2}^n \frac{i}{\log i} > \sum_{i=n/2}^n \frac{i}{\log i} > \sum_{i=n/2}^n \frac{n/2}{\log(n/2)} = \frac n2\frac{n/2}{\log(n/2)} > \frac n2\frac{n/2}{\log n} = \frac14 \frac{n^2}{\log n}, $$ which is the same order of magnitude as the upper bound.

Moral of the story: when the "trivial bound" (in this case, number of terms times the minimum term) isn't strong enough, try breaking the object into pieces and using the trivial bound on each piece separately.

Answer 2

As you wrote $$T_n=T_1+\sum_{i=2}^n \frac i{\log(i)}$$ Since $$\int_2^k \frac x{\log(x)} dx=\text{Ei}(2 \log (k))-\text{Ei}(2\log (2))$$ $$\int_2^n \frac x{\log(x)} dx < T_n-T_1 <\int_2^{n+1} \frac x{\log(x)} dx$$ A very good approximation is $$T_n-T_1=\text{Ei}\left(2 \log \left(\frac{2n+1}{2}\right)\right)-\text{Ei}(2\log (2))$$

Using Euler-MacLaurin summation $$T_n -T_1\sim \frac{n^2 (2 \log (n)+1)}{4 \log ^2(n)}+\frac{n}{2 \log (n)}+C$$