# Closed form solution for recurrence

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!

-
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

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

-
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).

-