Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.