# Solve the recurrence relation: $T(n) = T(n - \sqrt{\mathstrut n}) + T(\sqrt{\mathstrut n}) + O(n)$

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.

• Why can't $T(n) = 0$ for all $n$. Or $T(n) = n$ for all $n$. – mathworker21 Apr 21 '19 at 10:57
• @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. – therealak12 Apr 21 '19 at 11:24
• what conditions do you have on $T(n)$? All I see is that $T(n) = T(n-\sqrt{n})+T(\sqrt{n})+O(n)$. – mathworker21 Apr 21 '19 at 11:49
• 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, ...?). – Einar Rødland Apr 21 '19 at 11:53
• @EinarRødland I edited my question and added some details. – 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.$$