Asymptotic behaviour of a recurrence relation - How to solve

Question

I'm going over a chapter in recurrence relations in preparation for job interviews and came across the following. I'd like to gain some better understanding of how to solve such a question.

Find a function F(n), that satisfies the recurrence F(n) = 2F($\sqrt{n}$) +1 for all n $\in$ $\mathbb{N}$

Then how do I find a big-O estimation for F(n)?

Answer 1

There is no function that satisfies the conditions for $n \in \mathbb N$ since not all $\mathbb N$ have a square root. However you can generalize to $n \in \mathbb R$:

Try constructing a function $G$ in terms of $F$, the common choices are:

$$G(n) = F(n^2)$$ $$G(n) = F(2^n)$$ $$G(n) = F(\log_2 n)$$ $$G(n) = F(\sqrt{n})$$

However, for this problem, the best these choices will get you is that one of them will give you $G(n)$ in terms of $G(n/2)$:

$$G(n) = F(2^n) = 2F(\sqrt{2^n}) + 1 = 2F(2^{n/2}) + 1 = 2G(n/2) + 1$$

So repeating the process, we choose:

$$H(n) = G(?? n ??)$$

in such a way that $H(n)$ can be written in terms of $H(n - 1)$.

$$H(n) = G(2^n) = 2G(2^n / 2) + 1 = 2G(2^{n - 1}) + 1 = 2H(n - 1) + 1$$

Now you solve the recursion for $H$, and use that to find $G$, and use that to find $F$.