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