Since log (n) is in base 2, the solution of the recurrence function looks like this:
T(n) = 2*T( sqrt(n) ) + log(n)
Substituindo n = 2^m
T(2^m) = 2*T( sqrt(2^m) ) + log(2^m)
T(2^m) = 2*T( 2^(m/2) ) + m
Considering the following transformation:
S(m) = T(2^m)
Temos:
S(m) = 2*S(m/2) + m
We can replace m = 2 ^ x
S(2^x) = 2*S( 2^(x-1) ) + 2^x
And we can be substituting recursively
S( 2^(x-1) ) = 2*S( 2^(x-2) ) + 2^(x-1)
S( 2^(x-2) ) = 2*S( 2^(x-3) ) + 2^(x-2)
S( 2^(x-3) ) = 2*S( 2^(x-4) ) + 2^(x-3)
...
Getting:
S(2^x) = 2*[2*[2*[...] + 2^(n-2)] + 2^(n-1)] + 2^n
Doing until S (1) and solving the summation we have:
S(2^x) = 2^x*S(1) + x*2^x
Como S(1) = 1
S(2^x) = 2^x + x*2^x
Substituting n = 2 ^ x
S(n) = n + log(n)*n
This is the solution of the S(n) = 2*S(n/2) + n
recurrence function that is isomorphic to the function we want by the S(n)=T(2^n)
So replacing
S(m) = T(2^m)
T(2^m) = S(m) = m + log(m)*m
And finally replacing n = 2 ^ m we have:
m = log(n)
T(n) = log(n) + log( log(n) )*log(n)
This is the solution of the given recurrence function and therefore it has the following complexity:
O(T(n)) = log(n) * log( log(n) )