Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need to find a closed form solution for the following recurrence:

$T(m) \leq T(\sqrt m) + 1$, $T(1)=1$

I honestly don't have even have an idea where to start. Help would be greatly appreciated!

share|improve this question
1  
You have $M$ and $m$ in your recurrence relation –  Amr Dec 17 '12 at 9:13
    
Sorry for the typo. I fixed it. –  mort Dec 17 '12 at 9:14
    
Why do you have $\leq$ –  Amr Dec 17 '12 at 9:22
    
In this case I can only give you an inequality –  Amr Dec 17 '12 at 9:22
    
The recurrence gives a time bound for Valiant fast merge algorithm on a PRAM. –  mort Dec 17 '12 at 9:27

2 Answers 2

$$T(m^{2^{0}})-T(m^{2^{-1}})\leq 1$$ $$T(m^{2^{-1}})-T(m^{2^{-2}})\leq 1$$ $$.$$ $$.$$ $$.$$ $$T(m^{2^{-(n-1)}})-T(m^{2^{-n}})\leq 1$$

Add all inequalities (notice that the sum in the LHS is telescoping): $$T(m)-T(m^{2^{-n}})\leq n$$ $$T(m)-n\leq T(m^{2^{-n}})$$

share|improve this answer
    
Is this a closed form? –  mort Dec 17 '12 at 9:29
    
No. this is probably the most I can do. –  Amr Dec 17 '12 at 9:29
    
Is T continuous at 1 –  Amr Dec 17 '12 at 9:30
    
There is no additional info on T. –  mort Dec 17 '12 at 9:34
    
Then probably thats it –  Amr Dec 17 '12 at 9:35

If you're willing to give up the initial $T(1)=1$ and only define $T$ on $(1, \infty)$ then if we denote $\lg m =\log_2m$, a closed-form solution (with equality, even) is $$ T(m) = a + \lg\lg m $$ where $a$ is an arbitrary real number. To see this, observe $$ \begin{align} T(\sqrt{m})+1&=(a+\lg\lg\sqrt{m})+1\\ &= a+1+\lg\lg(m^{1/2})\\ & =a + 1 +\lg\left(\frac{1}{2}\lg m\right)\\ &= a + 1 + \lg\left(\frac{1}{2}\right)+\lg\lg m\\ &= a + 1 - 1 +\lg\lg m\\ &= a+\lg\lg m = T(m) \end{align} $$ To see that I didn't just pull this out of thin air, the usual way to deal with recurrences involving $\sqrt{m}$ is to write the definition with $m=2^{2^k}$, as Amr did, and expand like this: $$ \begin{align} T(2^{2^k}) &= T(2^{2^{k-1}})+1\\ &= T(2^{2^{k-2}})+1+1\\ &= T(2^{2^{k-3}})+3\\ &= T(2^{2^{k-4}})+4\\ \end{align} $$ and so on, until you come to $T(2^{2^k}) = T(2^{2^0})+k$ (which is also why the initial value of such recurrences is usually taken to be 2, rather than 1).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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