The cost of the algorithm using the main theorem

Question

Hi can anyone help me with a 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) 

Application of the main theorem here

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

now stuck.

Answer 1

You have:

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

The second case of the main theorem applies if:

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

Where:

 c = log_b(a) 

Experiencing this, we have:

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

Thus, the second case applies. Thus, the solution to the problem of repetition:

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

Substituting m , we return to

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

Answer 2

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

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

Aggregation of the above equation for k = 1 - d gives T (2 ^ (2 ^ d)) = theta (d ^ 2). Let n = 2 ^ (2 ^ d), we obtain T (n) = theta ((log log n) ^ 2).