How do I find an upper bound on this recurrence
For definiteness, let's assume that the recurrence is
$$
f(n) = \begin{cases}
f(\lfloor n-\sqrt{n} \rfloor) + 1 &amp; n &gt; 0 \\
0 &amp; n = 0.
\end{cases}
$$
(We assume that the domain is the non-negative integers.)

Since $\lfloor n-\sqrt{n} \rfloor &gt; n-\sqrt{n}-1$, we see that
$$
f(n) \geq \frac{n}{\sqrt{n}+1} = \Omega(\sqrt{n}).
$$
In the other direction, let us note that $f(n)$ is monotone and that
$$
f(n) \leq f(\lfloor n/2 \rfloor) + \frac{\lceil n/2 \rceil}{\sqrt{\lceil n/2 \rceil}}.
$$
This is because until the parameter gets down to $\lfloor n/2 \rfloor$ (or smaller), the decrease at every step is at least $\sqrt{\lceil n/2 \rceil}$. This shows that
$$
f(n) \leq f(\lfloor n/2 \rfloor) + \sqrt{\lceil n/2 \rceil} \leq f(\lfloor n/2 \rfloor) + \sqrt{n/2} + 1.
$$
Iterating this $\log_2 n+1$ times, we get
$$
\begin{align*}
f(n) &amp;\leq f(\lfloor n/2 \rfloor) + \sqrt{n/2} + 1 \\ &amp;\leq
f(\lfloor n/4 \rfloor) + \sqrt{n/2} + \sqrt{n/4} + 2 \\ &amp;\leq \cdots \\ &amp;\leq
f(0) + \sqrt{n/2} + \sqrt{n/4} + \cdots + \sqrt{n/2^{\log_2 n + 1}} + \log_2n + 1 \\ &amp;\leq
\sqrt{n} \sum_{t=1}^\infty \frac{1}{\sqrt{2}^t} + O(\log n) \\ &amp;= O(\sqrt{n}).
\end{align*}
$$
We conclude that $f(n) = \Theta(\sqrt{n})$.