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

(Change of variables method)

Put $n = 2^m$

**$m = log_2n$**

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

Let $S(m) = T(2^m)$, which gives $S(\frac{m}{a}) = T(2^{\frac{m}{a}})$

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

since $T(b)=1$ and we assumed $S(m) = T(2^m)$ so if $2^m$ = $b$

$T(2^m) = 1$ so $m=log_2b$

$S(log_2b) = 1$

$S(m) = S(\frac{m}{a^2}) + 1+1$

$S(m) = S(\frac{m}{a^2}) + 2$

$S(m) = S(\frac{m}{a^3}) +1 + 2$

$S(m) = S(\frac{m}{a^3}) + 3$

**.**

**.**

**.**

**$S(m) = S(\frac{m}{a^k}) + k$**

**---------------------------------------------------------------------------------------------------------------**

as $S(log_2b) = 1 ,\frac{m}{a^k} = log_2b$ to make$ S(\frac{m}{a^k})$ equal to 1

$m = log_2n$

$\frac{log_2n}{a^k} = log_2b$

$\frac{log_2n}{log_2b} =a^k$

make base b by base change rule

$\frac{log_bn}{log_bb} =a^k$

${log_bn} =a^k$

apply $log_a$ on both sides

$k=log_alog_bn$

**$S(m) = S(\frac{m}{a^k}) + k$**

**$S(m) = 1+ log_a log_bn$**

**$ = Θ(log_a log_bn) $**