# Interesting Recurrence Relation $T(n) = T(\sqrt{n}) + T(n-\sqrt{n}) + n$

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. – 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 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

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) 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 Narain May 12 '12 at 22:16
show 1 more comment

## 1 Answer

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$

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 12, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9241833090782166, "perplexity_flag": "middle"}