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