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$
🎥 Video solution / Text Solution of this question is given below:
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)$