UGC NET CSE | December 2018 | Part 2 | Question: 21

Question

The solution of recurrence relation:

$T(n) = 2T (\sqrt{n}) + \lg(n)$ is

• A. $O(\lg(n))$
• B. $O(n \lg  (n))$
• C. $O(\lg  (n) \lg (n))$
• D. $O(\lg  (n) \lg(\lg  (n)))$

Answer 1

By recursively applying the recurrence relation, we got

$T(n) = 2^k . T(n^{\frac{1}{2^k}}) + k . \lg n$

By taking Base condition, $T(2) = 1$ ( I assumed it, in the question they haven’t specified it )

$n^{\frac{1}{2^k}} = 2 \implies 2^k = \log_2n \text{ and } k = \log_2(\log_2n)$

$\therefore T(n) = \log_2n . T(2) + \log_2(\log_2n) . \log_2n$

$\therefore T(n) = \log_2n + \log_2(\log_2n) . \log_2n = \lg \;n + \lg\;n . (\lg\lg\;n) = O(\lg n . (\lg\lg\;n) ) $

Answer 2

$Given,T(n)=2*T(n^{1/2})+log(n)\\ Now,this\ looks\ like\ an\ irregular\ form\ so\ we\ have\ to\ try\ to\ convert\ it\ into\ a \ known\ Master's\ Theorem\ form.Let's\ perform\ some\ substitutions\ as\ follows \\Assume,z=log(n),e^{z}=n,e^{z/2}=n/2\\ \therefore T(e^{z})=2*T(e^{z/2}) + z \\ As\ we're\ dealing\ with\ bounds\ this\ can\ be\ re-written\ as\\ T(z)=2*T(z/2)+z,which\ doesn't\ makes\ much\ difference\ as\ this\ function\ behaves\ almost\ the\ same\ as\ the\ previous\ one\\ Now,this\ form\ looks\ familiar\ to\ a\ regular\ Master's\ Theorem\ applicable\ form.\\ a=2,b=2,log_{b}a=1=power\ of\ g(n)(\therefore\ second\ form\ of\ the\ theorem\ is\ applicable)\\or,T(z)=O(z^{log_{b}a}*log(z))\\or,T(z)=O(z*log(z))\\ Now,putting\ the\ original\ variable"n"\ back\ in\ the\ equation\ we\ get:\\ T(n)=O(log(n)*log(log(n)))...(\because z=log(n))$

So,1 is the ans

Answer 3

Option 1 is right.

Comments

from step 3 to step 4,

2^m is written as m

2^(m/2) is written as m/2

But why  'm' is written as 'm' ? Previously you converted 2^m to m