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}$?

  • $\begingroup$ "at each step $n$ decreased...": what ?? $\endgroup$
    – user16034
    Apr 20, 2022 at 12:05
  • $\begingroup$ At each step of our recurrence, $n$ decrased by at least $\sqrt{\frac{n}{2}}$. $\endgroup$
    – ErroR
    Apr 20, 2022 at 12:11
  • $\begingroup$ ??? In a step $n$ is constant ??? $\endgroup$
    – user16034
    Apr 20, 2022 at 12:12
  • $\begingroup$ 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}}$? $\endgroup$
    – ErroR
    Apr 20, 2022 at 12:21
  • $\begingroup$ If you are asking if $n-\sqrt n<n-\sqrt{\dfrac n2}$, the answer is yes. "$n$ decreases" is a language abuse. $\endgroup$
    – user16034
    Apr 20, 2022 at 12:46

1 Answer 1


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})$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.