# prove upper bound of the recurrence $T(n) =T(n-\sqrt{n})+1$

i want to prove upper bound of the following recurrence $$T(n) =T(n-\sqrt{n})+1$$ is $$O(\sqrt{n})$$.

• What have you tried? Nov 1, 2020 at 16:03
• Proving this formally is more involved than it might first seem. Nov 1, 2020 at 20:46

Define a sequence by $$n_0 = n$$, $$n_{i+1} = n_i - \sqrt{n_i}$$. Let $$\ell$$ be the maximal index such that $$n_\ell \geq n/2$$. For $$i \leq \ell$$ we have $$\sqrt{n_i} \geq \sqrt{n/2}$$, and so $$n/2 \leq n_\ell \leq n - \ell \sqrt{n/2}$$. It follows that $$\ell \leq \sqrt{n/2}$$.
Let $$\ell_t$$ be the maximal index such that $$n_{\ell_t} \geq n/2^t$$; so $$\ell_0 = 0$$ and $$\ell_1 = \ell$$. The preceding paragraph shows that $$\ell_{t+1} - \ell_t \leq \sqrt{n_{\ell_t}/2}$$. Since $$n_{\ell_t+1} < n/2^t$$, it follows that $$n_{\ell_t} - \sqrt{n_{\ell_t}} < n/2^t$$. If $$t \leq \log_2 n$$ then $$n_{\ell_t} \geq 1$$, and so $$(\sqrt{n_{\ell_t}}-1)^2 = n_{\ell_t} - 2\sqrt{n_{\ell_t}} + 1 \leq n_{\ell_t} - \sqrt{n_{\ell_t}} < n/2^t$$, and so $$\sqrt{n_{\ell_t}} < \sqrt{n/2^t} + 1$$. Therefore if $$n_{\ell_t} \geq 1$$ then $$\ell_{t+1} - \ell_t \leq \sqrt{n/2^{t+1}} + 1/2$$. It follows that if $$t \leq \log_2 n$$ then $$\ell_{t+1} \leq \sqrt{n/2} + \cdots + \sqrt{n/2^{t+1}} + t/2 = O(\sqrt{n} + t).$$ Choosing $$t = \lfloor \log_2 n \rfloor$$, we get that the maximal index $$s$$ such that $$n_s \geq 1$$ is at most $$\ell_{t+1} = O(\sqrt{n} + \log n) = O(\sqrt{n})$$.
This shows that assuming an initial condition of the form $$T(n) = O(1)$$ for $$n \leq 1$$, you can bound $$T(n) = O(\sqrt{n})$$; a matching lower bound is obvious (at each step, the value of the parameter decreases by at most $$\sqrt{n}$$).
Using similar ideas, you can show that if you replace $$\sqrt{n}$$ by its floor or ceiling, then the resulting recurrence still grows like $$\Theta(\sqrt{n})$$.
What is the constant factor in the asymptotics of $$T(n)$$? If we define $$\tau(s) = n_s$$ and think of $$\tau$$ as continuous, then $$\tau' = -\sqrt{\tau}$$, and so $$\tau(s) = (c-s)^2/4$$. Since $$\tau(0) = n$$, we find that $$c = 2\sqrt{n}$$, and so $$\tau(s) = (2\sqrt{n}-s)^2/4$$. Therefore $$\tau(s) = 0$$ for $$s = 2\sqrt{n}$$, and so we expect $$T(n) \sim 2\sqrt{n}$$. This is indeed borne out by experiments, which suggest that $$T(n) = 2\sqrt{n} - \Theta(\log n)$$.