How to calculate Big O of $T(n) = aT(n^b) + f(n)$?
How to calculate Big O of $T(n) = aT(n^b) + f(n)$ with $0&lt;b&lt;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.