I have the following recurrence, and I want to upper bound how long it takes to terminate.
$R(0) = n$
$R(t) = R(t-1) - \max\left(1, \left\lfloor\sqrt{R(t-1)}\right\rfloor\right)$
The recurrence stops when $R(\cdot)=0$. Is there a way to determine how many iterations can occur before reaching $0$ for any positive integer $n$? Experimentally it seems to end at $t\leq 2 \sqrt{n}$, but I am not sure why.
Let $n_k$ be the smallest value of $n$ s.t. we will need at least $k$ iterations. We want to prove $k \leq 2 \sqrt{n_k}$, or, equivalently, $n_k \geq \frac{k^2}{4}$.
It's true for $k = 1$: $n_1 = 1 \geq \frac{1}{4}$. Assuming it's true for some $k$, lets prove it for $k + 1$.
We have $$n_{k + 1} - \sqrt{n_{k + 1}} \geq n_k \tag{*}$$ (otherwise after first iteration from $n_{k + 1}$ we will get number less than $n_k$, which will require less than $k$ more iterations for a total of at most $k$).
Assume that $n_{k + 1} < \frac{k^2 + 2k + 1}{4}$. As $n_{k + 1}$ is integer, it implies $n_{k + 1} \leq \frac{k^2 + 2k}{4}$. As function $x - \sqrt{x}$ monotonically increases when $x > 1$, this implies $$n_{k + 1} - \sqrt{n_{k + 1}} \leq \frac{k^2}{4} + \frac{k}{2} - \sqrt{\frac{k^2}{4} + \frac{k}{2}} < \frac{k^2}{4} \leq n_k$$ - contradiction with $(*)$. So $n_{k + 1} \geq \frac{(k + 1)^2}{4}$, and our statement is proven by induction.