Solving a peculiar recurence relation

Question

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 because $a = \omega(1)$ doesn't necessarily mean that $a$ is a constant (or is it ?) and hence Master's Theorem is not applicable. Following the same line of reasoning, this also means that $b$ may not be a constant, but that would make "$T(b) = 1$" condition meaningless. Can anyone help clear out my misconceptions (if any) ?

Thanks

Answer 1

In my opinion the problem statement seems poorly posed. It's not clear what is meant by the problem statement.

Normally, if we write $a$ or $b$ the assumption is that they are a constant: they do not depend on $n$. If they are intended to be a function of $n$, then they should be written as $a(n)$ or $b(n)$. Since that wasn't done, the only assumption I can see that makes sense is to assume they are constants. But then if they are constants, then writing $a,b = \omega(1)$ doesn't seem to me to make sense.

So, I suggest you go talk to your instructor to ask them what they had in mind and how one should interpret the question. We can't solve the question until we know what the question is asking.

Basically, I am validating that the confusion you are having seems reasonable: it seems reasonable to me to be confused about that, as I find the problem statement confusing.