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

What is the asymptotic rate of growth of the following recurrence?

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

Since I cannot use the Master's Theorem here, I could not figure it out the answer. My initial guess is $$n^{3/2}$$, but I'm not sure.

Can anyone help me? What are the big-O and big-Omega complexities here?

• If we assume that you mean $T(n)=n + T(n - \sqrt{n})$, it's easy to see, that rough estimation gives $O(n)$, so less, then you expected. Apr 26 at 23:10

You can get a lower bound of $$\Omega(n^{3/2})$$ as follows. Consider the number of steps it takes to get from $$n$$ to $$n/2$$. Since at each step, $$n$$ decreases by at most $$\sqrt{n}$$, this takes at least $$\sqrt{n}/2$$ steps. At each such step, we accumulate at least $$n/2$$, for a total of at least $$n^{3/2}/4$$.
You can prove a matching upper bound using a similar approach. While the input parameter is at least $$n/2$$, it decreases by at least $$\sqrt{n/2}$$, and so it takes at most $$\sqrt{n/2}$$ steps to get to $$n/2$$. During each such step, we accumulate at most $$n$$, for a total of at most $$n^{3/2}/\sqrt{2}$$. An identical argument shows that at most $$(n/2)^{3/2}/\sqrt{2}$$ is accumulated while going from $$n/2$$ to $$n/4$$, and so on. Hence $$T(n) \leq \frac{n^{3/2}}{\sqrt{2}} \left(1 + \frac{1}{2^{3/2}} + \frac{1}{4^{3/2}} + \cdots\right) = O(n^{3/2}),$$ since the geometric series inside the parentheses converges.
Numerical experiments suggest that $$T(n) \sim \frac{2}{3} n^{3/2}.$$ We can show this heuristically as follows. Let us imagine that $$T$$ is a recurrence in continuous time. Then $$T(n) - T(n-\sqrt{n}) \approx \sqrt{n} T'(n)$$, and so $$T'(n) \approx \sqrt{n}.$$ Integrating, we get $$T(n) \approx \frac{n^{3/2}}{3/2} = \frac{2}{3} n^{3/2}.$$ This can probably be showed by running the argument above more carefully (replacing $$n/2$$ with $$(1-\epsilon)n$$).