0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)$... $\endgroup$ – gt6989b May 8 '17 at 15:40
  • $\begingroup$ Can u give some rudimentary proof? Thanks in advance:) $\endgroup$ – Vk1 May 8 '17 at 15:41
0
$\begingroup$

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

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