1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ "at each step $n$ decreased...": what ?? $\endgroup$ Apr 20 at 12:05
  • $\begingroup$ At each step of our recurrence, $n$ decrased by at least $\sqrt{\frac{n}{2}}$. $\endgroup$
    – ErroR
    Apr 20 at 12:11
  • $\begingroup$ ??? In a step $n$ is constant ??? $\endgroup$ Apr 20 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 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$ Apr 20 at 12:46

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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