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 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$ – AK 12 Apr 21 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 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 at 11:53
  • $\begingroup$ @EinarRødland I edited my question and added some details. $\endgroup$ – AK 12 Apr 21 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.