Complexity of $T(n)=T(n - \sqrt{n})+n$

Question

What is complexity of $T(n)=T(n - \sqrt{n})+n$
I tried to solve this with a few methods that I know but none of them helped me. So I decided to ask you for help.

Answer 1

Assuming $T$ is monotone, defined on the reals, and usual assumptions for the recurrence relation to make sense (i.e., not having to deal with corner cases and floors/ceilings).

We will show that $T(n) = \Theta(n^{3/2})$.

• Why? The reason to assume this is the right thing to prove is heuristic: $$ T(n) = T(n-\sqrt{n})+ n \simeq T(n-2\sqrt{n})+ 2n-\sqrt{n} \simeq T(n-k\sqrt{n})+ kn-(k-1)\sqrt{n} $$ and we get $T(1)$ for $k\simeq\sqrt{n}$, which leads to $T(n) \simeq k\sqrt{n} \simeq n^{3/2}$. Of course, there were a lof of approximations made at every step, so we may want to actually prove it.

• Upper bound. Suppose there exists $C\geq 1$ such that $T(k) \leq Ck^{3/2}$ for every $k<n$. (The base case is easy, we just need $C$ to be chosen greater than the first few terms of $T$). Then $$ T(n) = n + T(n-\sqrt{n}) \leq n + C(n-\sqrt{n})^{3/2} \leq Cn + C(n-\sqrt{n})^{3/2} \leq C n^{3/2} $$ using the fact that $$ x^{3/2} \geq (x-\sqrt{x})^{3/2} + x, \qquad x\geq 1\,. $$ (To see why this is true, observe that, dividing both sides by $x^{3/2}$, this is equivalent to $1-1/\sqrt{x} \geq (1-1/\sqrt{x})^{3/2}$).

• Lower bound. Same thing, by induction. Suppose $T(k) \geq ck^{3/2}$ (for some small $c\in(0,1/2)$ chosen based on the first terms $T(1),\dots$) for every $k<n$. Then $$ T(n) = n + T(n-\sqrt{n}) \geq n + c(n-\sqrt{n})^{3/2} \geq n + c(n^{3/2}-2n) \geq cn^{3/2} $$ since $c\leq 1/2$, and using that $$ (x-\sqrt{x})^{3/2} \geq x^{3/2} - 2x,\qquad x\geq 1 $$ (shown e.g. via calculus).