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

  • 0
    @RahulNarain you are right. I edited the problem – 2012-05-14

1 Answers 1

2

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$