2
$\begingroup$

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 ?

Improve this question
$\endgroup$
6
  • 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$ Commented Oct 3, 2012 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$ Commented Oct 3, 2012 at 22:23
  • $\begingroup$ @TsuyoshiIto May be that the $\lg \lg u$ is a wrong way to slove it ? $\endgroup$ Commented Oct 3, 2012 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$ Commented Oct 3, 2012 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$ Commented Oct 3, 2012 at 23:02

1 Answer 1

Reset to default
4
$\begingroup$

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*} $$

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ It would be better to label a hint as a hint. For a solution, you cannot “forget about the +1.” $\endgroup$ Commented Oct 3, 2012 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$ Commented Oct 4, 2012 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.