Give asymptotic upper and lower bound for $T(n)$ given below. Assume $T(n)$ is constant for $n\le 2$.

$T(n)=4T(\sqrt n)+\lg^2 n$

Let,

$m=\lg n$

So,

$n=2^m$

Also,

$\sqrt n=2^{m/2}$

Now define:

$S(m)=T(2^m)$

Then recurrence becomes:

$S(m)=4S(m/2)+m^2$

Using Master Theorem:

$a=4,\ b=2$

$m^{\log_b a}=m^{\log_2 4}=m^2$

Here,

$f(m)=m^2$

So,

$S(m)=\theta(m^2\lg m)$

Now put $m=\lg n$:

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

So,

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