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.

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.
