What is the correct representation of Master Theorem?

Question

What I'm taught in my class -

$T(n)=aT(\frac{n}{b})+\theta(n^k\log^pn)$
where $a\geq1$, $b>1$, $k\geq1$ and $p$ is a real number.

1. if $a>b^k$ then, $T(n)=\theta(n^{\log_ab})$
2. if $a=b^k$ then,
   • if $p>-1$, then $T(n)=\theta(n^{\log_ab}\log^{p+1}n)$
   • if $p = -1$, then $T(n)=\theta(n^{\log_ab}\log\log n)$
   • if $p<-1$, then $T(n)=\theta(n^{\log_ab})$
3. if $a<b^k$, then
   • if $p\geq 0$, then $T(n)=\theta(n^k\log^pn)$
   • if $p<0$, then $T(n)=O(n^k)$

On certain websites, the above representation for Master Theorem is slightly different as follows -

$T(n)=aT(\frac{n}{b})+\theta(n^k(\log n)^p)$

This ambiguity creates a great confusion while solving problems such as :

What is the value of the recurrence : $T(n)=T(\sqrt{n})+\theta(\log\log n)$

Substituting $n=2^m$, we get a new expression :

$S(m)=S(\frac{m}{2})+\theta(\log m)$
Here $a=1$, $b=2$, $k=0$ and $p=1$

If I apply Master Theorem as per the way I am taught in class, the result I get is :

$T(n)=\theta(\log\log\log n)$

and if I solve using the other formula, I get the result as :

$T(n)=\theta((\log\log n)^2)$

Which is the correct one? This confusion is making me question every problem that I've solved.

Answer 1

By convention, the notation $log^p(x)$ is defined to be $(log(x))^p$, not $p$ iterations of the $log$ function. This is similar to the trigonometric functions, which gives us identities like $sin^2(x)+cos^2(x)=1$.