1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – ankit Feb 14 at 8:18
  • 1
    $\begingroup$ 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))$ $\endgroup$ – Cesareo Feb 14 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.