What is complexity of $T(n)=T(n - \sqrt{n})+n$
I tried to solve this with a few methods that I know but none of them helped me. So I decided to ask you for help.
Asked
Active
Viewed 84 times
0
-
3Which few methods? – Clement C. Jul 25 '18 at 18:13
-
@alxchen The induction is not quite correct, but the asymptotics are right. Under some mild assumptions on $T$ (monotone, etc.), we get $T(n) \sim_{n\to\infty} \frac{2}{3}n^{3/2}$. – Clement C. Jul 25 '18 at 18:19
-
Thanks. Could you prove it? – Iman Roostaei Jul 25 '18 at 18:29
-
1Yes, I can. (Proving that without the exact constant is not too hard.) But you, can you answer the question from my first comment? What have you tried, and how/why did it fail? – Clement C. Jul 25 '18 at 18:29
-
I tried solving it by 1) changing the variable 2) guessing and using induction 3) transform relation to some kind which could be solved by the general formula. – Iman Roostaei Jul 25 '18 at 18:39
-
And 2. above does not work, given the guess $CT^{3/2}$ (for some big enough constant $C>0$)? Why? – Clement C. Jul 25 '18 at 18:41
-
Also, be wary of "general formula" things. They are not that general, and lock your thinking into specific tracks. – Clement C. Jul 25 '18 at 18:42
1 Answers
3
Assuming $T$ is monotone, defined on the reals, and usual assumptions for the recurrence relation to make sense (i.e., not having to deal with corner cases and floors/ceilings).
We will show that $T(n) = \Theta(n^{3/2})$.
Why? The reason to assume this is the right thing to prove is heuristic: $$ T(n) = T(n-\sqrt{n})+ n \simeq T(n-2\sqrt{n})+ 2n-\sqrt{n} \simeq T(n-k\sqrt{n})+ kn-(k-1)\sqrt{n} $$ and we get $T(1)$ for $k\simeq\sqrt{n}$, which leads to $T(n) \simeq k\sqrt{n} \simeq n^{3/2}$. Of course, there were a lof of approximations made at every step, so we may want to actually prove it.
Upper bound. Suppose there exists $C\geq 1$ such that $T(k) \leq Ck^{3/2}$ for every $k<n$. (The base case is easy, we just need $C$ to be chosen greater than the first few terms of $T$). Then $$ T(n) = n + T(n-\sqrt{n}) \leq n + C(n-\sqrt{n})^{3/2} \leq Cn + C(n-\sqrt{n})^{3/2} \leq C n^{3/2} $$ using the fact that $$ x^{3/2} \geq (x-\sqrt{x})^{3/2} + x, \qquad x\geq 1\,. $$ (To see why this is true, observe that, dividing both sides by $x^{3/2}$, this is equivalent to $1-1/\sqrt{x} \geq (1-1/\sqrt{x})^{3/2}$).
Lower bound. Same thing, by induction. Suppose $T(k) \geq ck^{3/2}$ (for some small $c\in(0,1/2)$ chosen based on the first terms $T(1),\dots$) for every $k<n$. Then $$ T(n) = n + T(n-\sqrt{n}) \geq n + c(n-\sqrt{n})^{3/2} \geq n + c(n^{3/2}-2n) \geq cn^{3/2} $$ since $c\leq 1/2$, and using that $$ (x-\sqrt{x})^{3/2} \geq x^{3/2} - 2x,\qquad x\geq 1 $$ (shown e.g. via calculus).
Clement C.
- 67,323