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