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

Question

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.

Answer 1

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