# How can I show h(n) = O( √ n)?

Is there any way to make recursion tree that satisfies the height $$h(n) = h(n−\sqrt{n}) + 1$$ to show $$h(n) = O(\sqrt{n})$$?

Hint: Suppose that $$n = 2^{2^k}$$. Hence:
$$h(n) = h(2^{2^k} - 2^{2^{k-1}}) + 1 = h((2^{2^k} - 2^{2^{k-1}}) - \sqrt{2^{2^k} - 2^{2^{k-1}}}) + 1 + 1 = h(2^{2^k} - 2^{2^{k-1}} - 2^{2^{k-2}}\times \sqrt{2^{2^{k-1}}-1}) + 1 + 1$$
From the expansion, the order of $$2^{2^{k-1}} = \sqrt{n}$$ times is the length of the tree.
Consider the following sequence: $$a_0 = n$$, $$a_{t+1} = a_t - \sqrt{a_t}$$. You are interested in the minimum $$t$$ for which $$a_t$$ falls behind some arbitrary constant $$C > 0$$ (this corresponds to the base case of your recursion).
Here is the basic idea. As long as $$a_i \geq n/4$$, the sequence is decreasing at a rate of at least $$\sqrt{n}/2$$. Therefore after at most $$(n-n/4)/(\sqrt{n}/2) = \alpha \sqrt{n}$$ steps (where $$\alpha = 3/2$$), you dip below $$n/4$$. After at most $$\alpha \sqrt{n/4}$$ steps, you dip below $$n/4^2$$. And so on. It takes at most $$\alpha \sqrt{n/4^r}$$ to dip below $$n/4^{r+1}$$. The total number of steps to reach $$C$$ is thus at most $$\alpha\sum_{r=0}^\infty \sqrt{n/4^r} = \alpha\sqrt{n} \sum_{r=0}^\infty 2^{-r} = 2\alpha\sqrt{n}.$$ With more effort, you should be able to determine the constant in front of $$\sqrt{n}$$.
Note also the trivial $$\sqrt{n} - O(1)$$ lower bound, which follows from the fact that the sequence decreases by at most $$\sqrt{n}$$ each step.