Recursive complexity with change of variable
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*}
$$