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

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?

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

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.