Master's Theorem & $T(n)=2T(n^{1/2})+\log n$

Master's Theorem Statement (standard)

For $T(n)=aT(n/b)+f(n)$, $a≥1$, $b>1$, $c=\log_b a$:

• Case1 $f(n)=O(n^{c-ε}) → Θ(n^c)$
• Case2 $f(n)=Θ(n^c\log^k n)→Θ(n^c\log^{k+1}n)$
• Case3 $f(n)=Ω(n^{c+ε})$ + regularity → Θ(f)
  (Requires $n/b$ form, not $n^{1/2}$.)

Can Master Apply to $T(n)=2T(\sqrt n)+\log n$?

Not directly — argument is $n^{1/2}$, not $n/b$ with constant $b$. Standard master not applicable. Use substitution / change of variable.

Solution via Domain Transformation

Let $n=2^m$ (assuming $n$ is power of 2 for asymptotics), define $S(m)=T(2^m)$.
Then:
$$S(m)=T(2^m)=2T((2^m)^{1/2})+\log(2^m)=2T(2^{m/2})+m =2S(m/2)+m$$
Now $S(m)=2S(m/2)+m$ → This is master form with $a=2$, $b=2$, $f(m)=m$.

• $c=\log_2 2=1$, $f(m)=m=Θ(m^1)=Θ(m^c)$ → Case2 → $S(m)=Θ(m\log m)$.

Convert back: $m=\log n$ →
$$T(n)=S(\log n)=Θ(\log n · \log \log n)$$

Result: $$T(n)=Θ(\log n \cdot \log\log n)$$
Alternatively $O(\log n \log\log n)$.

Verification via Recursion Tree

Depth: each level halves $m$ → $\log m$ levels = $\log\log n$ levels; work per level $Θ(m)$ → total $Θ(m\log m)$.