## Solving a peculiar recurence relation

Given recurrence:

$$T(n) = T(n^{\frac{1}{a}}) + 1$$ where $$a,b = \omega(1)$$ and $$T(b) = 1$$

The way I solved is like this (using change of variables method, as mentioned in CLRS):

Let $$n = 2^k$$

$$T(2^k) = T(2^{\frac{k}{a}}) + 1$$

Put $$S(k) = T(2^k)$$ which gives $$S(\frac{k}{a}) = T(2^{\frac{k}{a}})$$

$$S(k) = S(\frac{k}{a}) + 1$$

Now applying Master’s Theorem,

$$S(k) = \Theta(log_2(k))$$

$$T(2^k) = \Theta(log_2(k))$$

$$T(n) = \Theta(log_2log_2(n))$$

I believe my method is incorrect. Can anyone help ?

Thanks