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

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

• My hunch is, you are right -- you have $\lg n$ terms in the expansion, and a noticeable portion of them are of size $O(n \lg n)$... – gt6989b May 8 '17 at 15:40
• Can u give some rudimentary proof? Thanks in advance:) – Vk1 May 8 '17 at 15:41

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