Algorithm cost using master theorem

Question

Can anyone please help me with this question?

T(n)=T(n^(1/2)) + theta (lg lg n)

This is what I have done so far.

Let:

m = lg n
s(m)=s(m/2) + theta (lg m)

Applying the master theorem here

a=1 b=2
m^log 2 (1) = m^0 =1 

Now I'm stuck.

Answer 1

You have:

a = 1, b = 2
f(m) = Ө(lg(m))

The second case of the master theorem applies if:

f(m) = Ө(m^c * lg^k(m))

where:

c = log_b(a)

Testing this out, we have:

f(m) = Ө(lg(m)) = Ө(m^0 * lg(m)) 
-> c = 0
-> c = log_b(a) = log_2(1) = 0

So the second case does apply. The solution to the recurrence is therefore:

T(m) = Ө(m^c * lg²(m)) = Ө(lg²(m))

Substituting m, we arrive back at

T(n) = Ө(lg²(lg(n)))

Answer 2

First, T(n) = T(n^(1/2)) + theta(lg lg n) can be written as

T(2^(2^k)) = T(2^(2^(k-1))) + theta(k).

Aggregating the above equation for k=1 to d gives T(2^(2^d)) = theta(d^2). Let n=2^(2^d), we obtain T(n) = theta( (lg lg n)^2 ).