2
$\begingroup$

I am trying to find the time complexity for the recurrence $T(n) = 2T(n^{1/2}) + \log n$. I am pretty close to the solution, however, I have run into a roadblock. I need to solve $n^{{1/2}^k} = 1$ for $k$ to simplify my substitution pattern. I am not looking for answers to the recurrence, just a solution for $k$. Any help would be appreciated. Thanks

  • 0
    please use latex2012-10-27
  • 0
    Either $n=1$, and any $k$ goes, or $n\ne1$, and no $k$ solves the equation.2012-10-27
  • 0
    This does not make much sense. After all, if $n\ne1$ then $n^x=1$ has only the solution $x=0$, and with $x=1/2^k$, that is impossible. Did we change the meaning of the question in editing it?2012-10-27
  • 1
    You do not want $n^{1/2^k}$ to be $1$ to solve the recurrence. You just need $n^{1/2^k}$ small i.e. $\mathcal{O}(1)$ so that $T(\mathcal{O}(1)) = \mathcal{O}(1)$.2012-10-27

2 Answers 2