Recurrence $T(n - \sqrt{n}) + 1$

Question

I am confused on how to go about this recurrence. I tried utilizing the Master Theorem and the substitution method, but I was not able to get to a solution.

$$T(n) = T(n - \sqrt{n}) + 1.$$

I know if the problem were $T(n) = T(n - \sqrt{n})$, it would be $O(1)$ since $T(n) = T(n - \sqrt{n}) = T(m)$ with $0 < m < n$ and $T(\varepsilon)$ would be $0$.

But I am not understanding how the $+1$ would affect the asymptotic tight bound.

Answer 1

Hint. By solving $y-\sqrt y=x$ find $a_n\uparrow\infty$ such that $T(a_{n+1})=T(a_n)+1$, hence $T(a_n)=n+O(1)$. Then show that $a_n\sim n$ asymptotically to conclude that $T(n)=\Theta(n)$.