# solve $n^{{1/2}^k} = 1$ for $k$

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

-
please use latex –  MSKfdaswplwq Oct 27 '12 at 20:33
Either $n=1$, and any $k$ goes, or $n\ne1$, and no $k$ solves the equation. –  Did Oct 27 '12 at 20:38
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? –  Harald Hanche-Olsen Oct 27 '12 at 20:41
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)$. –  user17762 Oct 27 '12 at 20:42

The non-symbolic way to think of it is that $k$ is the number of times you can take the square root of $n$ before you get to a constant (let's say 2 to make things easier later). So it is the inverse of how many times it takes to square 2 before you get (around) to your number $n$.

$$2, 4, 16, 256, 65536, 4G,...$$ or $2^{2^k}$.

'$\log$' doesn't work, that's only for multiples of 2, not squaring.

'$\log^{*}$' also doesn't work, that's only for towers of 2, $2^{2^{2^ .\ ^2}}$, not squaring.

How do you get $k$ from $n = 2^{2^k}$. Just take log twice.

$$\log 2^{2^k} = 2^k$$

so

$$\log \log 2^{2^k} = k$$

Now that is the depth of your tree, and you can add up all the $\log n$ parts at each node to get the solution.

-

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)$. To solve the recurrence, proceed as follows. $$T(n) = 2 T(n^{1/2}) + \log n$$ Setting $n = x^{2^{m}}$, we get that $$T(x^{2^m}) = 2 T(\sqrt{x^{2^m}}) + 2^m \log (x) = 2T(x^{2^m/2}) + 2^m \log (x) = 2T(x^{2^{m-1}}) + 2^m \log (x)$$ Denoting $T(x^{2^m}) = g_x(m)$, we then get \begin{align} g_x(m) & = 2g_x(m-1) + 2^m \log(x) = 2(2g_x(m-2) + 2^{m-1} \log(x)) + 2^m \log(x)\\ & = 4g_x(m-2) + 2^m \log(x) + 2^m \log(x)\\ & = 8g_x(m-3) + 2^m \log(x) + 2^m \log(x) + 2^m \log(x)\\ & = 2^mg_x(0) + \underbrace{2^m \log(x) + 2^m \log(x) + 2^m \log(x) + \cdots 2^m \log(x)}_{m \text{ such terms}}\\ & = 2^mg_x(0) + m2^m \log(x) \end{align} $$T(n) = T(x) \dfrac{\log n}{\log x} + m \log n = T(x) \dfrac{\log n}{\log x} + \left(\dfrac{\log \log n - \log \log x}{\log 2}\right) \log n$$ Hence, $$T(n) = \mathcal{O}(\log n \times \log \log n)$$

-