recategorized by
834 views

3 Answers

Best answer
2 votes
2 votes
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) ) $
edited by
0 votes
0 votes

$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

0 votes
0 votes

Option 1 is right.

Answer:

Related questions

11 votes
11 votes
1 answer
1
0 votes
0 votes
2 answers
2
Arjun asked Jan 2, 2019
2,363 views
​​​​​Match List-I with List-II and choose the correct answer from the code given below :$\begin{array}{|c|c|c|c|} \hline & \textbf{List I} & & \textbf{List II} ...
1 votes
1 votes
1 answer
3
Arjun asked Jan 2, 2019
5,634 views
​​A box contains six red balls and four green balls. Four balls are selected at random from the box. What is the probability that two of the selected balls will be re...