Solving recurrence using recurrence trees. I have a recurrence which I know has the solution $O(\lg n)$, it looks like this:
$$T(n) = T(\sqrt n) + \lg n$$ 
If I understand correctly, the recurrence tree method involves looking for the term that moves towards 1 the fastest, find a general formula for this term, then set it equal to 1 and solve it. 
Looking at the pattern I found that it should satisfy this equation:
$$n^\frac{1}{2^k} = 1$$
Where $k$ is the tree-level. Further solving gives me:
$$2^k = \log(n-1)$$
$$k = \frac{\log(\log(n-1))}{\log(2)}$$
Now, if I wouldn't have known that the solution is $O(\lg n)$, my best guess in this situation would probably be $O(\lg \lg n)$. 
Can somebody please help me understand how to properly analyze this equation?
 A: Here, if you substitute $n = 2^m$, equation becomes,
$$ T(2^m) = T(2^{m/2})+ m,$$ 
Now substitute again,  S(m) = $ T(2^m)$, so equation turns to 
$$ S(m) = S(m/2) + m $$ Now this can be solved using Masters method.
As you mentioned I try to solve that way, I am not very sure if its right still this might help, you can see the term $\sqrt n $ can't be brought down to 1, it can be brought closer to 1 , so if we define our function as 
\begin{align}
\ T(n) & = T(\sqrt n) + logn,\quad if \; n>2 \\
  & =  1 \qquad \qquad \qquad  if \; n\le 2\\  
\end{align}
So we have a tree rooted at n, with branching factor of 1 and work done at each level is $ log n^{1/2^k} $,
Now if we take $ 1/2^k = m $ , so this T(n) terminates when $ n^m = 2 $
On solving it we get k = $ loglog_2n$
So the total work done by T(n) would be $log n + log n^{1/2} + log n^{1/4} + \ldots  + log n ^{log log_2 n} $, then
T(n) = $ logn^{1 + 1/2 + 1/4 + \ldots + loglog_2n} $
A: I'm using Master theorem to solve this recurrence relation. 
Given recurrence relation is :
$$T(n) = T(\sqrt{n}) + lg(n)$$
$$T(n) = T(\sqrt{n}) + costant.log(n)$$
$$T(n) = T(n^{1/2}) + log(n)$$
Let $k = log(n)$, then $n = 2^k$, so
$$T(2^k) = T(2^{k/2}) + k$$
Assume, $T(2^k) = S(k)$, so $T(2^{k/2}) = S(k/2)$, Then recurrence relation became 
$$S(k) = S(k/2) + k$$

The master theorem concerns recurrence relations of the form:
$$T(n) = aT(n/b) + f(n)$$ where $a \geq 1 , b>1$
Now using Master theorem case $(3)$
If $f(n) = \Omega(n^c)$, where $c < log_b(a)$
   and if it is also true that:
$af(n/b) \leq kf(n)$ for some constant $k < 1$ and sufficiently large $n$ (often called the regularity condition). Then :
$$T(n) = \Theta(f(n))$$

Therefore, 
$k = \Omega(k^c)$, where $c < log_2(1)$
Then : $$S(k) = \Theta(k)$$
$$T(n) = \Theta(log_2(n))$$
