# Recurrence using Master Theorem and Back-Substitution

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.

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$$

• Thank you for the answer. Can you please explain the meaning of the statement "for parameters 'a' and 'b' both of which are ω(1)." ? and Also can you please explain why 2 methods which I have described in the question are giving different answers ? – ankit Feb 14 at 8:18
• Think that $\log_a(\log_b n) = \frac{\log_2(\log_2 n)-\log_2(\log_2 b)}{\log_2 a}\approx \Theta(\log_2(\log_2 n))$ – Cesareo Feb 14 at 9:19