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

@goxul I had troubles solving this. But now I got this.

But can you tell me how long should I continue expansion and which terms should I ignore?

---

Oh, that part.

We keep on expanding till we reach the base case - because for the base case, we can plug in the value directly. In this case, I've assumed that the base case is $T(2) = 1$. We will reach this point when $n^{1/2^{k}}$ becomes equal to two. For that case, we'll get $k = \log \log n$. Once we get that, notice $T(n^{1/2^{k}})$ becomes one, as $T(2) = 1$.

I hope this makes sense.

---

Got it.

Thanks a lot for the help.

If you have time, take look at this question. Here is where I don't know when to approximate and when to ignore some terms.

---

Hi goxul.

Can you please post the calculation of k. Just want to know how approximation is done.

---

Is the base condition correct?

Putting T(2) in LHS and RHS in equation 1 should give the right value?

---

@'JEET $n^{1/2^k} = 2 \implies \frac{1}{2^k} \log n = 1 \implies \log n = 2^k \implies k = \log \log n$

---

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.