prove upper bound of the recurrence $ T(n) =T(n-\sqrt{n})+1 $
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} &lt; n/2^t$, it follows that $n_{\ell_t} - \sqrt{n_{\ell_t}} &lt; 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}} &lt; n/2^t$, and so $\sqrt{n_{\ell_t}} &lt; \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)$.