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