Recursive complexity with change of variable I face a problem with computing a complexity. 
I have this equality : $P(u) = (\sqrt{u}+1)P(\sqrt{u}) + \theta(\sqrt{u})$

And I want to prove that $P(u) = O(u)$

This is how I process :

I put $m = \lg\lg u \implies P(u) = P(2^{2^{m}}) = (2^{2^{m-1}}+1)P(2^{2^{m-1}}) + \theta(2^{2^{m-1}})$

Now, I consider $S(m)$ that is : $S(m) = P(2^{2^{m}}) = mS(m-1) + \theta(m-1)$

And here I have a problem. I obtain a factorial complexity and I don't know how to integrate $\lg$ to prove the equality $P(u) = O(u)$

Some advice ?
Following your suggestion, let $S(m) = P(2^{2^m})$, and let's forget about the $+1$ in the recurrence. Then
$$
\begin{align*}
S(m) &amp;= 2^{2^{m-1}}S(m-1) + \Theta(2^{2^{m-1}}) \\ &amp;=
\Theta(2^{2^{m-1}} + 2^{2^{m-1}+2^{m-2}}) + 2^{2^{m-1}+2^{m-2}} S(m-2) \\ &amp;= \cdots \\ &amp;=
\Theta(2^{2^{m-1}} + 2^{2^{m-1}+2^{m-2}} + \cdots + 2^{2^{m-1}+\cdots+1}) \\ &amp;=
%\Theta(2^{2^m-1}(1+2^{-1}+2^{-1-2}+\cdots+2^{-1-2-\cdots-2^{m-2}})) \\ &amp;=
\Theta(2^{2^m}(2^{-1}+2^{-2}+\cdots+2^{-2^{m-1}})) = \Theta(2^{2^m}).
\end{align*}
$$