Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)

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$





Solution

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)$


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More
Ask Your Question or Put Your Review.

loading...