1
$\begingroup$

I stumbled about this recursive function today:

$f_n = f_\sqrt{n} + \sqrt n$

I tried to solve it with substitution ($m = \log_2 n, \quad g_{2^m} = g_{2^{m/2}} + 2^{m/2}$), but I have a bad feeling with this result ($f_n \in \Theta(\sqrt n)$). Am I doing something wrong here? Could someone please explain me how to solve this recurrence function exactly?

1 Answers 1

1

First, $f(x)\geqslant\sqrt{x}$ as soon as $f(x)\geqslant0$ for every $x\geqslant0$. On the other hand, if $f(x)\leqslant2\sqrt{x}+c$, then $f(x^2)\leqslant2\sqrt{x}+c+x\leqslant2x+c$ for every $x\geqslant4$.

This proves that, for $c$ large enough, $\sqrt{x}\leqslant f(x)\leqslant2\sqrt{x}+c$ for every $x\geqslant1$, and in particular that $f(x)=\Theta(\sqrt{x})$.

With a little more work, one can show that $f(x)/\sqrt{x}\to1$ when $x\to+\infty$ hence the asymptotics is given by the lower bound given above and the factor $2$ in the upper bound is a mere artefact.