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
 A: 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)$$
A: 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.
