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
solve $n^{{1/2}^k} = 1$ for $k$
2
$\begingroup$
logarithms
recurrence-relations
-
0please use latex – 2012-10-27
-
0Either $n=1$, and any $k$ goes, or $n\ne1$, and no $k$ solves the equation. – 2012-10-27
-
0This 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
-
1You 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