# Interesting Recurrence Relation $T(n) = T(\sqrt{n}) + T(n-\sqrt{n}) + n$

I found an interesting recurrence that I do not know how to solve. I think this has to do with quicksort with pivots at rank $\sqrt{n}$. I do not know how to approach this problem nor found any helpful resources about it.

Here is the recurrence:

$$T(n)=T(\sqrt{n})+T(n−\sqrt{n})+n$$ Any help would be much appreciated. Thanks!

Let's say the base case is T(N) where N < 2 is $O(1)$

• I think you have to specify what $n$ is, and give some context, Doing what comes naturally I find the contradiction: T(0)=2T(0). T(0)=0. T(1)=T(1)+T(0)+1. T(0)=-1. – Mark Bennet May 12 '12 at 20:10
• maybe it is recurence for exact square integers(for integers,from which we can take always square root – dato datuashvili May 12 '12 at 20:13
• @dato: Mark used the recurrence for n=0 and for n=1, which are both exact square integers. – Did May 12 '12 at 20:15
• @dato 0 and 1 are squares. If I plug $n=1$ into the equation I need the value of T(0), so I can't exlude 0. If I put in $n=4$, I need T(2) etc – Mark Bennet May 12 '12 at 20:17
• It's really the asker's responsibility to clarify the question, but given the context of analysis of quicksort, I would guess that the actual recurrence ought to be $T(0) = T(1) = 1$ and $T(n) = T(\lfloor\sqrt n\rfloor) + T(n-\lfloor\sqrt n\rfloor) + n$ for $n \ge 2$. – Rahul May 12 '12 at 22:16

If I just worry about asymptotics and ignore the issue of whether the square root is an integer, I would guess $T(n)\approx bn^a$. Substituting that in gives $bn^a= bn^{a/2}+b(n-\sqrt n)^a+n\approx bn^{a/2}+bn^a-ban^{a-\frac 12} +n$ which is correct to the first two orders if $a=\frac 32, b=\frac 23$