# What is the height of a tree with recursion formula: $T(n) = T(n - \sqrt{n})$

I know if the time complexity of an algorithm is given with the above formula, then the algorithm works in constant time but my question is that what will be the height of the recursion tree for this formula?

• @"AK 12" If you meant, for example, $T(n)=T(n-\sqrt n) + 1$ or $T(n)=T(\lfloor n-\sqrt n\rfloor) + 1$, please update your post. – John L. Jun 11 '19 at 12:22
• @Apass.Jack Sorry for the mistake. I edited the post and replaced "linear" with constant. My question is that how many steps does it take to reach T(0) ? – AK 12 Jun 12 '19 at 12:41

If you are asking how many iterations of the function $$x\mapsto x-\sqrt x$$ does it take to get from $$n$$ below $$1$$:

For a lower bound, the resulting sequence is nonincreasing, hence you remove at most $$\sqrt n$$ at each step, hence you need at least $$\frac n{\sqrt n}=\sqrt n$$ steps.

For an upper bound: in order to get from $$n$$ to $$n/2$$, all the steps will remove at least $$\sqrt{n/2}$$, hence $$\frac{n/2}{\sqrt{n/2}}=\sqrt{n/2}$$ steps are enough for that. By the same argument, $$\sqrt{n/4}$$ steps are enough to get from $$n/2$$ to $$n/4$$, $$\sqrt{n/8}$$ from $$n/4$$ to $$n/8$$, etc. The total number of steps is bounded by the geometric series $$\sqrt n\left(\sqrt{1/2}+\sqrt{1/4}+\sqrt{1/8}+\cdots\right)=\sqrt n\frac{\sqrt{1/2}}{1-\sqrt{1/2}}=\frac{\sqrt n}{\sqrt 2-1}\approx2{.}4\sqrt n.$$

Thus, the required number of steps is $$\Theta(\sqrt n)$$; a more precise argument would show that it is $$\bigl(2+o(1)\bigr)\sqrt n$$.

• Special thanks! Exactly what I needed. – AK 12 Jun 13 '19 at 16:19

Clearly T(n) = T(0) for all n. Which is constant, not linear. Is that really the question you wanted to ask?

And I just see a mathematical relation. I can’t see any recursion or tree or algorithm here.

• Sorry for the mistake. I edited the post and replaced "linear" with constant. My question is that how many steps does it take to reach T(0) ? – AK 12 Jun 12 '19 at 9:04
• The recursion tree of the function int f(int n) { if (n=1) return 1; else return f(n-sqrt(n)); } (or whatever base case is actually intended). – David Richerby Jun 12 '19 at 16:04