# Is there a simpler solution for this recuurence?

Consider this recurrence relation, $$T(n)=T(n-\sqrt{n})+1$$ I try to show that $$T(n)=O(\sqrt{n})$$.

Also, I read this link, but my question is, can I claim that, at each step $$n$$ decreased by at least $$\sqrt{\frac{n}{2}}$$ to reach $$\frac{n}{2}$$?

• "at each step $n$ decreased...": what ??
– user16034
Apr 20, 2022 at 12:05
• At each step of our recurrence, $n$ decrased by at least $\sqrt{\frac{n}{2}}$. Apr 20, 2022 at 12:11
• ??? In a step $n$ is constant ???
– user16034
Apr 20, 2022 at 12:12
• No, $n$ isn't constant. At the first step we have $n-\sqrt{n}$ at the next step we have $n-\sqrt{n}-\sqrt{n-\sqrt{n}}$. My question is, can we claim at each step we decrease $n$ by at least $\sqrt{\frac{n}{2}}$? Apr 20, 2022 at 12:21
• If you are asking if $n-\sqrt n<n-\sqrt{\dfrac n2}$, the answer is yes. "$n$ decreases" is a language abuse.
– user16034
Apr 20, 2022 at 12:46

I'm assuming that the base case is $$T(n)=1$$ for $$n\le 1$$. If you accept the fact that $$T(\cdot)$$ is an increasing function, you can show by induction on $$m \ge 1$$ that $$T(m^2) < 2m$$.

If $$m \le 1$$ then the claim is trivially true. Assume now that the claim holds for $$m \ge 1$$. You have: \begin{align*} T((m+1)^2) &\le T((m+1)^2 - (m+1)) + 1 = T(m^2 + 2m +1 - m-1) +1 \\ &= T(m^2 + m) + 1 = T(m^2 + m -\sqrt{m^2+m})+2\\ &\le T(m^2)+2 < 2m+2=2(m+1). \end{align*}

Then $$T(n) = O(\sqrt{n})$$ follows by choosing $$m = \lceil \sqrt{n} \rceil$$ since $$T(n) \le T(m^2) < 2(m+1) < 2(\sqrt{n} +2) = O(\sqrt{n})$$.