Doubt

Question

How to get solution of the following recurrence?

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

Comments

very good question

somebody please tell

Answer 1

This is one of the method for solving this question

Comments

Thanks a lot, nice solution! I am seeing this division by 2^k step for the first time. Could you guide on any resource which presents this? Thanks

Answer 2

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

Dividing both sides by $n$, we get

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

Now, let $S(n) = \frac{T(n)}{n}$

So, the recurrence equation boils down to

$S(n) = S(\sqrt{n}) + 1$

Let, $n = 2^{k}$

So, $S(2^{k}) = S(2^{\frac{k}{2}}) + 1$

Again, let $H(k) = S(2^{k})$

So, $H(k) = H(k/2) + 1$

Solving the equation by master theorem, we get

$S(2^{k}) = H(k) = logk$

Now, since $n = 2^{k}$, $k = logn$

So, $S(n) = loglogn$

Since, $S(n) = \frac{T(n)}{n}$,

$T(n) = nS(n)$

$T(n) = nloglogn$

Comments

Clear doubt.