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?