1
$\begingroup$

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!

  • 0
    All decreasing sequences. How about that?2012-12-17

2 Answers 2

1

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

  • 0
    Ok, thanks. I'll let you know the answer when I got it.2012-12-17
0

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