0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Feb 15 '20 at 3:40
  • 1
    $\begingroup$ Why do you believe your method is incorrect? Have you tried checking whether your candidate solution satisfies the recurrence? Do you have a specific question about your approach? $\endgroup$ – D.W. Feb 15 '20 at 3:40
  • $\begingroup$ @D.W. Because of $a = \omega(1)$ condition (we can't assume $a$ is a constant right ?). I'm confused with the specified conditions: $a,b = \omega(1)$ and what they signify in this context - If we treat them as variables, wouldn't $T(b) = 1$ become meaningless ?. This was a question in an exam and many are claiming that the answer is $\Theta(log_alog_b(n))$ $\endgroup$ – Debasish Das Feb 15 '20 at 16:56
2
$\begingroup$

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.

$\endgroup$

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.