Question

T(n) = sqrt(n) * T(sqrt(n)) + n

 

Given solution is O(log log n). But my solution is O(n log log n).

'wolframalpha'' shows the answer same as mine. You can find the solution here.

 

Can anyone confirm the solution and provide an explantion?

Comments

@gmrishikumar

after i commented here, i saw similar question which was beautifully solved using master theorem;

watch this

https://gateoverflow.in/249658/recurrence-relation-mit 

---

@Gate Fever The solution is nicely done.

---

@Shaik Masthan in 2nd question you shown,

$T(n)=\sqrt{n}T(\sqrt{n})+\sqrt{n}$

in the 3rd last line …

from this line, 

$=n^{1-1/2^{k}}+n^{1-1/2^{k-1}}+.........................n^{1-1/2^{2}}+n^{1-1/2^{1}}$

how below line comes. it is only possible if if all the elements are multiply but it’s in addition.

=  $n^{(1+1+1+...........1)-(1/2^{k}+1/2^{k-1}+.................+1/2)}$  

isn’t it?? 

PS:

$=n^{1-1/2^{k}}.n^{1-1/2^{k-1}}..........................n^{1-1/2^{2}}.n^{1-1/2^{1}}$  if this written then answer comes what you have written.

Answer 1

Given, $T(n) = \sqrt{n} T(n) + n$.

After the first substitution,we notice that:

$T(n) = \sqrt{n}[n^{1/4} T(n^{1/4}) + \sqrt{n}] + n \implies T(n) = \sqrt{n}[n^{1/4} T(n^{1/4})] + 2n $.

Continuing this series, after $k$ substitutions, we get:

$T(n) = n^{\sum_{i=1}^{k}\frac{1}{2^i}}T(n^{1/2^{k}}) + kn$.

Assuming base case as two, we'll get $k = \log \log n$.

After this, it's pretty much only calculations. Let me know if you don't get it, I'll type it out.

Comments

Thanks.

---

@Shaik Masthan

i didnt get this part

$\frac{n}{n^{\frac{1}{2^{k}}}} ==> n / 2 $

---

$\frac{1}{2^k}$ = ${(2^k)}^{-1}$ ===> substitute ${(2^k)}$ = log n

then $\frac{1}{2^k} = {(log_2n)}^{-1} = log_n2$

$n^{\frac{1}{2^k}} =n^{log_n2} = 2^{log_nn} = 2$

Answer 2

Refer this is an easy way.