0

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

gt6989b
  • 54,422
Vk1
  • 99
  • 1
    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 08 '17 at 15:40
  • Can u give some rudimentary proof? Thanks in advance:) – Vk1 May 08 '17 at 15:41

1 Answers1

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

gt6989b
  • 54,422