Solving the recurrence relation $T(n) = T(n-\sqrt n) + 1$ I have an algorithm that at each step can discard $\lceil\sqrt(n)\rceil$ possibilities at a cost $1$. The solution to the recurrence relation below is related to the question of complexity of such algorithm:
$$T(n) = T\left(n-\lceil\sqrt n\rceil\right) + 1$$
I know that: $T(0)=0$, $T(1) = 1$.
I tried substituting $n=2^{2^k}$ but it did not get me far.
 A: As did has already pointed out, $T(n)\sim2\sqrt{n}$. Any easy way to arrive at this conclusion is to pretend $T(n)$ is defined for all real numbers and continuous, and approximate
$$
1=T(n)-T(n-\lceil\sqrt{n}\rceil)\approx\sqrt{n}T'(n)
$$
for large $n$, which makes $T'(n)\approx1/\sqrt{n}$ and in turn, by integration, $T(n)\approx2\sqrt{n}$.
Computing $T(n)$ using Maple, indeed reveals that
$$
T(n)=2\sqrt{n}-\frac{\ln(2\sqrt{n}+1)}{\ln2}+\epsilon_n
$$
where $\epsilon_n\in[-0.1,1]$.
A more formal proof of $T(n)\sim2\sqrt{n}$ is possible, but a bit more technical.
Let's write $n'=n-\lceil\sqrt{n}\rceil$. Then,
$$
\left(\sqrt{n}-\tfrac{1}{2}\right)^2-\tfrac{5}{4}\le n-\sqrt{n}-1\le
n'
\le n-\sqrt{n}=\left(\sqrt{n}-\tfrac{1}{2}\right)^2-\tfrac{1}{4}.
$$
First, assume $T(k)\le2\sqrt{k}$ for $k<n$: this holds for $k<1$, which starts the induction. Then,
using $n'<(\sqrt{n}-1/2)^2$,
$$
T(n)=T(n')+1\le2\sqrt{n'}+1\le 2\left(\sqrt{n}-\tfrac{1}{2}\right)+1=2\sqrt{n}.
$$
Next, assume $T(n)\ge2\sqrt{n}-\tau(n)$ for some function $\tau(n)$. Using
$$
2\sqrt{n'} \ge \sqrt{(2\sqrt{n}-1)^2-5} \ge 2\sqrt{n}-1-\frac{5}{2\sqrt{n}-1},
$$
this makes
$$
T(n)=T(n')+1\ge 2\sqrt{n'}+1-\tau(n')
\ge 2\sqrt{n}-\frac{5}{2\sqrt{n}-1}-\tau(n'),
$$
and so $T(n)\ge 2\sqrt{n}-\tau(n)$ holds if we define $\tau(0)=0$ and
$$
\tau(n)=\tau(n')+\frac{5}{2\sqrt{n}-1}.
$$
In turn, we now have
$$
\frac{\tau(n)-\tau(n')}{n-n'}
=\frac{5}{(2\sqrt{n}-1)\cdot\lceil\sqrt{n}\rceil}
\le\frac{5}{(2\sqrt{n}-1)\cdot\sqrt{n}}
<\frac{5+\delta}{2n}
$$
for any $\delta>0$ and sufficiently large $n$. From this follows that $\tau(n)$ at worst is $O(\ln n)$.
A: Here is a geometric intuition.
We started with a width of $\sqrt{n}$. At each step, the width reduced by (1/2). Hence within roughly $2\sqrt{n}$ steps we reach the base case.
