I think that $T(\sqrt{\mathstrut n})$ part is $O(log(log(n)))$ but I cannot solve the whole problem. . Can anyone help?

Edit: The formula appears while solving the following problem:

If in quick-sort algorithm we choose the median of first $2\sqrt{\mathstrut n} + 1$ elements as the pivot element, what would be the time complexity of quick-sort in this case?

Answering the question we see every time the problem is divided into two sub-problems, first of size $\sqrt{\mathstrut n}$ and the other of size $n - \sqrt{\mathstrut n}$. So the recursive formula is as mentioned in the title.

  • $\begingroup$ Why can't $T(n) = 0$ for all $n$. Or $T(n) = n$ for all $n$. $\endgroup$ – mathworker21 Apr 21 '19 at 10:57
  • $\begingroup$ @mathworker21 what do you mean? Note that we know n is greater than or equal to 1, so $T(n)$ can't be equal to zero. $\endgroup$ – therealak12 Apr 21 '19 at 11:24
  • $\begingroup$ what conditions do you have on $T(n)$? All I see is that $T(n) = T(n-\sqrt{n})+T(\sqrt{n})+O(n)$. $\endgroup$ – mathworker21 Apr 21 '19 at 11:49
  • $\begingroup$ As it stands, any $T(n)=O(n)$ will satisfy the relation. It will even be satisfied for any $T(n)=an^u$ for $u\le3/2$. The $O(n)$ simply gives too much flexibility to lock down $T(n)$. You should also state where the problem comes from, and if there are any restrictions on $T$ (positive, increasing, ...?). $\endgroup$ – Einar Rødland Apr 21 '19 at 11:53
  • $\begingroup$ @EinarRødland I edited my question and added some details. $\endgroup$ – therealak12 Apr 21 '19 at 12:00

Assume that $T(n)$ is defined for all real $n\ge 1$ and $T(n)\le T(n-\sqrt{n})+ T(\sqrt{n})+Cn$ for some $C>0$ and all $n\ge 4$. We claim that a function $T(n)=\frac 23C n^{3/2}+D$, where $D\ge 0$. For this it suffices to remark that, by Lagrange’s Theorem, there exists $c\in (n-\sqrt{n},n)$ such that $$T(n)- T(n-\sqrt{n})=T’(c)\sqrt{n}\le Cc^{1/2}\sqrt{n}=Cn.$$


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.