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 ?

  • 2
    $\begingroup$ Please check your calculation in switching variables from u to m. If you define S(m)=P(2^(2^m)), then you should not get S(m)=mS(m−1)+Θ(m−1). $\endgroup$ – Tsuyoshi Ito Oct 3 '12 at 22:09
  • $\begingroup$ You may have right. Actually it's useless because I fall on the same formula as to the begining ... with squares $\endgroup$ – Jérôme Boé Oct 3 '12 at 22:23
  • $\begingroup$ @TsuyoshiIto May be that the $\lg \lg u$ is a wrong way to slove it ? $\endgroup$ – Jérôme Boé Oct 3 '12 at 22:51
  • $\begingroup$ Considering S(m)=P(2^(2^m)) is a good step, but you need some more calculation to say something useful about S(m). One way to proceed is to write S(m) in terms of S(m−1) (which you attempted but your calculation is incorrect; try to correct it), then write S(m) in terms of S(m−2), then write S(m) in terms of S(m−3), to see a possible pattern. If you see a pattern there, then you can use mathematical induction to prove that this observed pattern is indeed true. $\endgroup$ – Tsuyoshi Ito Oct 3 '12 at 22:59
  • $\begingroup$ 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}$. $\endgroup$ – 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*} $$

  • 2
    $\begingroup$ It would be better to label a hint as a hint. For a solution, you cannot “forget about the +1.” $\endgroup$ – Tsuyoshi Ito Oct 3 '12 at 23:12
  • $\begingroup$ @TsuyoshiIto Well, if you can prove that "$+1$" does not change the result then you can, but that is of course missing, too. $\endgroup$ – Raphael Oct 4 '12 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.