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

  • 8
    $\begingroup$ 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. $\endgroup$ – Mark Bennet May 12 '12 at 20:10
  • $\begingroup$ maybe it is recurence for exact square integers(for integers,from which we can take always square root $\endgroup$ – dato datuashvili May 12 '12 at 20:13
  • $\begingroup$ @dato: Mark used the recurrence for n=0 and for n=1, which are both exact square integers. $\endgroup$ – Did May 12 '12 at 20:15
  • 1
    $\begingroup$ @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 $\endgroup$ – Mark Bennet May 12 '12 at 20:17
  • $\begingroup$ 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$. $\endgroup$ – 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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