# 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)$

• @TsuyoshiIto May be that the $\lg \lg u$ is a wrong way to slove it ? – Jérôme Boé Oct 3 '12 at 22:51
• But before that, I think that it is easy to think if you remove the asymptotic notations from the assumption; the assumption implies that there is a constant a>0 such that for all u, it holds that $P(u)\le(\sqrt{u}+1)P(\sqrt{u})+a\sqrt{u}$. – Tsuyoshi Ito Oct 3 '12 at 23:02
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) &= 2^{2^{m-1}}S(m-1) + \Theta(2^{2^{m-1}}) \\ &= \Theta(2^{2^{m-1}} + 2^{2^{m-1}+2^{m-2}}) + 2^{2^{m-1}+2^{m-2}} S(m-2) \\ &= \cdots \\ &= \Theta(2^{2^{m-1}} + 2^{2^{m-1}+2^{m-2}} + \cdots + 2^{2^{m-1}+\cdots+1}) \\ &= %\Theta(2^{2^m-1}(1+2^{-1}+2^{-1-2}+\cdots+2^{-1-2-\cdots-2^{m-2}})) \\ &= \Theta(2^{2^m}(2^{-1}+2^{-2}+\cdots+2^{-2^{m-1}})) = \Theta(2^{2^m}). \end{align*}
• @TsuyoshiIto Well, if you can prove that "$+1$" does not change the result then you can, but that is of course missing, too. – Raphael Oct 4 '12 at 10:00