I received the following proof, can someone show all steps of how the solution was formed?
Proof:
Let n=2^2^k, then we have
T(n)=T(2^2^k)=2T(n^(1/2))+log n
***How do you get n^(1/2) equals 2^2^(k-1)
=2T(2^2^(k-1))+2^k
***How do you get 2T(2^2^(k-1)) equals 2(2T(2^2^(k-2))+2^(k-1))
=2(2T(2^2^(k-2))+2^(k-1))+2^k
=2^2*T(2^2^(k-2))+2*2^k
=2^2*(2T(2^2^(k-3))+2^(k-2))+2*2^k
=2^3*T(2^2^(k-3))+3*2^k
=...
=2^k*T(2^2^0)+k*2^k
=2^k*T(2)+k*2^k
=2^k+k*2^k
=(k+1)*2^k
Since n=2^2^k, then 2^k=lg n and k=lg lg n
Thus T(n)=theta((lg n)*(lg lg n))
***Please show intermediate steps