Resolve the recurrence for $T(n)=T(n-n/(\lg n))+ O(n\lg n)$

Question

The recurrence I am looking for is the following.

$$T(n)=T\left(n-\frac{n}{\lg n}\right)+ O(n\lg n)$$

Does it solve to $O(n\lg^2 n)$?

Answer 1

I think you want to do something like this: $$ \begin{split} T(n) &\le T\left(n-\frac{n}{\lg n}\right)+ Kn\lg n \\ &\le T\left(n-\frac{2n}{\lg n}\right) + Kn\lg n + K\left(\left(n-\frac{n}{\lg n}\right)\lg \left(n-\frac{n}{\lg n}\right)\right) \\ &\le T\left(n-\frac{2n}{\lg n}\right) + 2Kn\lg n \\ &\le \ldots \\ &\le T(0) + (\lg n) K n \lg n \\ &= O\left(n \lg^2 n \right) \end{split} $$

The only question is using the same $K$ in all inequalities with $n$ going down, but since the added term does not decrease here, it should be able to account for it...