Algorithm

Question

Solve

  $T\left ( n \right )=\sqrt{n}\, *\, T\left ( \sqrt{n} \right )\: +100n$

Comments

Ans $\Theta (log n)$?

Answer 1

$T\left ( n \right )=\sqrt{n}\, *\, T\left ( \sqrt{n} \right )\: +100n$

Let $n= 2^{k}$

$\Rightarrow T\left ( 2^{k} \right )= \left ( 2^{k} \right )^{1/2}\, *\, T\left ( \left ( 2^{k} \right )^{1/2}\right )+100*2^{k}$

$\Rightarrow T\left ( 2^{k} \right )= 2^{k/2}\, * \, T\left ( 2^{k/2} \right )+100*2^{k}$

$\Rightarrow $ dividing both side by $2^{k}$$\Rightarrow T\left ( 2^{k} \right )/2^{k}=T\left ( 2^{k/2} \right )/2^{k/2}+100$

Let $T\left ( 2^{k} \right )/2^{k}=Y\left ( k \right )$

$\Rightarrow Y\left ( k \right )=Y\left ( k/2 \right )+100$

Using Master theorem $a=1,b=2,k=0,p=0\Rightarrow a= b^{k}\Rightarrow case 2\Rightarrow Y\left ( k \right )=\Theta \left ( \log_{2}k\right )$

$\Rightarrow we\, have \, Y\left ( k \right )=\log_{2}k\, and \, we \, know \, that T\left ( 2^{k} \right )/2^{k}=Y\left ( k \right )$

$T\left ( 2^{k} \right )=2^{k}*\, Y\left ( k \right )\Rightarrow 2^{k}*\log_{2}k\Rightarrow n*\log \log n$

$\Rightarrow T\left (n\right )= \Theta \left ( n*\log \log n \right )$