0
$\begingroup$

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
    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.2012-05-12
  • 0
    maybe it is recurence for exact square integers(for integers,from which we can take always square root2012-05-12
  • 0
    @dato: Mark used the recurrence for n=0 and for n=1, which are both exact square integers.2012-05-12
  • 1
    @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) etc2012-05-12
  • 0
    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$.2012-05-12
  • 0
    @RahulNarain you are right. I edited the problem2012-05-14

1 Answers 1