Q) For parameters 'a' and 'b' both of which are $\omega(1)$, Now, consider the recurrence $T(n) = T(n^{1/a}) + 1$ with base condition $T(b) = 1$ Then $T(n)$ is :
I am not getting the meaning of statement : for parameters 'a' and 'b' both of which are $\omega(1)$. Can anyone please explain it. Does it mean 'a' and 'b' both are constants and greater than 1.
I have one more doubt if we solve using back- substitution then I am getting answer as $\Theta(log_alog_b n) $ but if I use change of variables and Master's theorem then answer is :
$T(n) = T(n^{\frac{1}{a}}) + 1$
So, why both methods are giving different answers. I know base does not matters in $\Theta$ notation here but I want to know the reason of different bases.
Please help. Thank you.
Hint.
Another method. Assuming $a > 0$, as
$$ T\left(a^{\log_a n}\right)=T\left(a^{\log_a (\frac na)}\right)+1 $$
calling $\mathcal{T}(\cdot) = T(a^{(\cdot)})$ and $u = \log_a n$ we have equivalently
$$ \mathcal{T}(z)=\mathcal{T}\left(\frac za\right)+1 $$
and now calling $\mathbb{T}(\cdot) = \mathcal{T}(a^{(\cdot)})$ and $u = \log_a z$ we arrive at the recurrence
$$ \mathbb{T}(u)=\mathbb{T}(u-1)+1 $$
with solution
$$ \mathbb{T}(u)=u+C_0 $$
following with $\mathbb{T}\to \mathcal{T}\to T$