1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.