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}$?
7
-
$\begingroup$ "at each step $n$ decreased...": what ?? $\endgroup$– user16034Apr 20, 2022 at 12:05
-
$\begingroup$ At each step of our recurrence, $n$ decrased by at least $\sqrt{\frac{n}{2}}$. $\endgroup$– ErroRApr 20, 2022 at 12:11
-
$\begingroup$ ??? In a step $n$ is constant ??? $\endgroup$– user16034Apr 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$– ErroRApr 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$– user16034Apr 20, 2022 at 12:46
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
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})$.
