3
$\begingroup$

I'm a student studying Big O. I know that we can solve $T(n) = aT(\frac{n}{b}) + f(n)$ by compering $n^{\log_b{a}}$ to $f(n)$ or

$O(n^{\log_b{a}} + f(n))$


Today I was faced with $T(n) = T(\sqrt n) + 1$ and I think it is $O(\log\log n)$. and I was faced with this too, $T(n) = T(\sqrt n) + O(\log\log n)$ that I think it is $O(\log^2\log n)$.

I'm wondering what is the formula (or method) to solve any kind of this type of problems (my guess is $O(f(n)a^n\log\log n)$). so:

How to calculate Big O of $T(n) = aT(n^b) + f(n)$ with $0<b<1$?

Thanks in advance.

$\endgroup$
4
$\begingroup$

How to calculate Big O of $T(n) = aT(n^b) + f(n)$ with $0<b<1$?

The powerful technique you are searching for is variable substitution.

Let $S(m)=T(2^m)$. Then $$S(m)=T(2^m)=aT(2^{mb}) + f(2^m)=aS(mb)+g(m),$$ where $g(m)=f(2^m)$.

Now that we have a recurrence relation about $S(m)$, to which we might be able to apply the master's theorem. Here are some examples.

  • If $f(n)$ is a constant, so is $g(m)$. If $a=1$ and $b=\frac12$, then we know that $S(m)=O(\log m)$. Hence, $$T(n)=S(\log n)=O(\log \log n).$$
  • If $f(n)=\log n$, $a=1$ and $b=\frac23$, then $S(m)=S(2m/3)+m$. So $S(m)=O(m)$. Hence,
    $$T(n)=S(\log n)=O(\log n).$$
  • If $f(n)=\log\log n$, $a=1$ and $b=\frac12$, then $S(m)=S(m/2)+\log m$. So $S(m)=O((\log m)^2)$. Hence,
    $$T(n)=S(\log n)= O((\log\log n)^2).$$

Note that the above reasoning is rather loose as $\log n$ and $\sqrt n$ might not be an integer when $n$ is. A lot of careful sandwiching together with some kind of continuity or monotonicity is needed to establish the result rigorously.

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