Solving a Recurrence relation formula with squared

Question

I Hope someone Can help me with that:

I will be asked to answer what is the runtime complexity of the algorithm. I tried to set m=2^ and still failed Thanks

Answer 1

Let n = 2^x

Then T(2^x) = T(2^√x) + 1

Let U(x) = T(2^x), so:

U(x) = U(√x)+1

We assume there is a base case, so U(x) ∈ O(log log x)

Substituting back:

T(2^x) ∈ O(log log x)

T(n) ∈ O(log log log n)