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