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

Question

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.

Answer 1

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.