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!

  • 1
    You have $M$ and $m$ in your recurrence relation2012-12-17
  • 0
    Sorry for the typo. I fixed it.2012-12-17
  • 0
    Why do you have $\leq$2012-12-17
  • 0
    In this case I can only give you an inequality2012-12-17
  • 0
    The recurrence gives a time bound for Valiant fast merge algorithm on a PRAM.2012-12-17
  • 0
    $T(m)\equiv1$ will satisfy your inequality. I think you need to be more specific.2012-12-17
  • 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
    Is this a closed form?2012-12-17
  • 0
    No. this is probably the most I can do.2012-12-17
  • 0
    Is T continuous at 12012-12-17
  • 0
    There is no additional info on T.2012-12-17
  • 0
    Then probably thats it2012-12-17
  • 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).