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

Question

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

Answer 1

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.

Answer 2

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.