Solve a recurrence relation with $\sqrt n$ inside.

Question

I have never seen such an equation:

$$T(n) = T\left(\frac n2 + \sqrt n\right) + n$$

Is it possible to solve?

If yes, how? I mean is there any general method for it or something?
thanks.

Answer 1

Try $T(n) = 2n + an^{1/2}+ b(n)$ where $b(n)$ is small compared with $n^{1/2}$
Treat $\sqrt{n}$ as small compared with $n$ or $n/2$. Solve for $a$, knowing you can correct for the square-root by changing $b(n)$
$$2n+a\sqrt{n}+b(n)=n+2\sqrt{n}+a\sqrt{n/2+\sqrt{n}}+b(n/2+\sqrt{n})+n$$ Cancel $2n$ from one side and $n+n$ from the other. To leading order, what remains is $$a\sqrt{n}=2\sqrt{n}+a\sqrt{n/2}+...$$ Solve for $a$, then go to the next-largest terms. (Hint: I think they are $O(\log n)$)

Answer 2

For every $c$, the property that $T(n)\leqslant2n+7\sqrt{n}+c$ is hereditary for every $n\geqslant10^4$. Likewise, for every $c$, the property that $T(n)\geqslant2n-c$ is hereditary for every $n$. One can choose $c$ large enough so that both properties are satisfied for every $n\leqslant10^4$, then $2n-c\leqslant T(n)\leqslant2n+7\sqrt{n}+c$ for every $n$. In particular, $T(n)\sim2n$ when $n\to\infty$.