Solve the recurrence relation:$ T(n) = \sqrt{n} T \left(\sqrt n \right) + n$ $$T(n) = \sqrt{n} T \left(\sqrt n \right) + n$$
Master method does not apply here. Recursion tree goes a long way. Iteration method would be preferable.
The answer is $Θ (n \log \log n)$.
Can anyone arrive at the solution.
 A: Let $n = m^{2^k}$. We then get that
$$T(m^{2^k}) = m^{2^{k-1}} T (m^{2^{k-1}}) + m^{2^{k}}$$
\begin{align}
f_m(k) & = m^{2^{k-1}} f_m(k-1) + m^{2^k} = m^{2^{k-1}}(m^{2^{k-2}} f_m(k-2) + m^{2^{k-1}}) + m^{2^k}\\
& = 2 m^{2^k} + m^{3 \cdot 2^{k-2}} f_m(k-2)
\end{align}
$$m^{3 \cdot 2^{k-2}} f_m(k-2) = m^{3 \cdot 2^{k-2}} (m^{2^{k-3}} f_m(k-3) + m^{2^{k-2}}) = m^{2^k} + m^{7 \cdot 2^{k-3}} f_m(k-3)$$
Hence,
$$f_m(k) = 2 m^{2^k} + m^{3 \cdot 2^{k-2}} f_m(k-2) = 3m^{2^k} + m^{7 \cdot 2^{k-3}} f_m(k-3)$$
In general, it is not hard to see that
$$f_m(k) = \ell m^{2^k} + m^{(2^{\ell}-1)2^{k-\ell}} f_m(k-\ell)$$
$\ell$ can go up to $k$, to give us
$$f_m(k) = km^{2^k} + m^{(2^{k}-1)} f_m(0) = km^{2^k} + m^{(2^{k}-1)} m^{2^0} = (k+1) m^{2^k}$$
This gives us $$f_m(k) = (k+1) m^{2^k} = n \left(\log_2(\log_m n) + 1\right) = \mathcal{O}(n \log_2(\log_2 n))$$ since $$n=m^{2^k} \implies \log_m(n) = 2^k \implies \log_2(\log_m(n)) = k$$
A: Use substitution method:
$$\Large\begin{align*} \text{T}(n) &= \sqrt{n}\ \text{T}(\sqrt{n})+n\\ &= n^{\frac{1}{2}}\ \text{T}\left(n^{\frac{1}{2}} \right )+n\\ &= n^{\frac{1}{2}}\left( n^{\frac{1}{2^2}}\ \text{T}\left(n^{\frac{1}{2^2}} \right )+n^{\frac{1}{2}} \right )+n\\ &= n^{\frac{1}{2}+\frac{1}{2^2}}\ \text{T}\left(n^{\frac{1}{2^2}}\right ) +n^{\frac{1}{2}+\frac{1}{2}}+n\\ &= n^{\frac{1}{2}+\frac{1}{2^2}}\ \text{T}\left(n^{\frac{1}{2^2}}\right ) +2n\\ &= n^{\frac{1}{2}+\frac{1}{2^2}}\left(n^{\frac{1}{2^3}}\ \text{T}\left(n^{\frac{1}{2^3}}\right ) +n^{\frac{1}{2^2}} \right )+2n\\ &= n^{\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}}\ \text{T}\left(n^{\frac{1}{2^3}}\right ) +n^{\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^2}} +2n\\ &= n^{\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}}\ \text{T}\left(n^{\frac{1}{2^3}}\right ) +3n\\ \vdots \\ &= n^{\sum_{i=1}^{k}\frac{1}{2^i}}\ \text{T}\left(n^{\frac{1}{2^k}}\right ) +kn\\ \end{align*}$$
assuming $\text{T}(2) = 2$, which is the least value of n that could be. So, $$\begin{align*} n^{\frac{1}{2^k}} &= 2\\ \frac{1}{2^k}\log_2(n) &= \log_2(2) \\ \log_2(n) &= {2^k} \\ \log_2\log_2(n) &= k\log_2(2) \\ \log_2\log_2(n) &= k \end{align*}$$
therefore, the recurrence relation will look like:
$$\large \begin{align*} \text{T}(n)&=n^{\sum_{i=1}^{k}\frac{1}{2^i}}\ \text{T}\left(n^{\frac{1}{2^k}}\right ) +kn\\ &=n^{\sum_{i=1}^{\log_2\log_2(n)}\frac{1}{2^i}}\ \text{T}\left(n^{\frac{1}{2^{\log_2\log_2(n)}}}\right ) +n \log_2\log_2(n)\\ \end{align*}$$
where, $$\sum_{i=1}^{\log_2\log_2(n)}\frac{1}{2^i} = 1-\frac{1}{\log_2(n)} = \text{fraction always, as }n\geq 2$$
so, $$\large \text{T}(n) = \mathcal{O}\left( n \log_2 \log_2 n \right)$$
A: Let $n=2^{2^u}$, thus we get:
$$T(2^{2^u})=2^{2^{u-1}}T(2^{2^{u-1}})+2^{2^{u}}$$ Now divide both sides by $2^{2^u}$ to get (Note that $2^{2^{u-1}}/2^{2^u}=2^{-2^{u-1}}$)
$$2^{-2^u}T(2^{2^u})=2^{-2^{u-1}}T(2^{2^{u-1}})+1$$
$$2^{-2^u}T(2^{2^u})-2^{-2^{u-1}}T(2^{2^{u-1}})=1$$
By summing from 1 to n we get:
$$2^{-2^n}T(2^{2^n})-2^{-1}T(2)=n$$
therefore:
$$T(2^{2^n})=2^{2^n}(2^{-1}T(2)+n)$$
A: Yes, the Master Theorem can be applied. Here's how:
$$T(n) = \sqrt{n} T(\sqrt{n}) + n = \sqrt{n} T(\sqrt{n}) + \mathcal{O}(n)$$
Let $n = 2^k$, $\sqrt{n} = 2^{k/2}$, and $k = \log{n}$. Substituting in above equation, we get:
$$T(2^k) = 2^{k/2} T(2^{k/2}) + 2^k \tag{1}$$
Dividing (1) by $2^k$, we get:
$$\frac{T(2^k)}{2^k} = \frac{2^{k/2}T(2^{k/2})}{2^k} + 1\tag{2}$$
Simpliifying $\frac{2^{k/2}}{2^k} = \frac{1}{2^{k/2}}$ in $(2)$ gives us:
$$\frac{T(2^k)}{2^k} = \frac{T(2^{k/2})}{2^{k/2}} + 1\tag{3}$$
Let $y(k) = \frac{T(2^k)}{2^k}$, then $(3)$ gives us:
$$y(k) = y\left(\frac{k}{2}\right) + 1\tag{4}$$
Now, we apply the Master Theorem ($T(n) = aT\left(\frac{n}{b}\right) + n^d$), where $a=1, b=2$, and $d=0$, $a=b^d = 1$.
Because $d=0$, we have:
$$y(k) = k^d\log{k} = \log{k}\tag{5}$$
But, we also know that $T(2^k) = 2^ky(k)$, then
$$T(2^k) = 2^k\log{k} \implies T(n) = n\log{\log{n}}$$
since $n=2^k$ and $k = \log{n}$.
Finally: $T(n) = \Theta(n\log{\log{n}})$
A: Solution with Detailed Explanation:
Master theorem cannot be applied here because for applying the Master theorem the number of sub-problems generated must be constant (a).
 T(n)=√n*T(√n)+n

 Let, m=lg n; n=2^m

Therefore,
 T(2^m)=2^(m/2)* T(2^(m/2)) + 2^m .....(i)

 Let, S(m)=T(2^m)

Therefore changing the equation (i) we get,
   S(m)=2^(m/2) * S(m/2) + 2^m .....(ii) //Level 1

   S(m/2)=2^(m/4) * S(m/4) + 2^(m/2) .....(iii)

   S(m/4)=2^(m/8) * S(m/8) + 2^(m/4) .....(iv)

   ....

   ....

   So on and so forth.

By putting value of S(m/4) from equation (iv) in equation (iii) we get,
     S(m/2)=2^(m/4) * [2^(m/8) * S(m/8) + 2^(m/4)] + 2^(m/2)  //Replaced value is inside [ ]

           =[(2^(m/4)*2^(m/8)) * S(m/8) + 2^(m/4) * 2^(m/4)] + 2^(m/2)

           =[(2^(m/4)*2^(m/8)) * S(m/8) + 2^(m/2)] + 2^(m/2) .....(v) //Level 2

By putting value of equation (v) in equation (ii) we get,
    S(m)=2^(m/2) * [[(2^(m/4)*2^(m/8)) * S(m/8) + 2^(m/2)] + 2^(m/2)] + 2^m

           =[(2^(m/2)*2^(m/4)*2^(m/8)) * S(m/8) + 2^(m/2) *2^(m/2)] + 2^(m/2) * 2^(m/2)] + 2^m

           =[(2^(m/2)*2^(m/4)*2^(m/8)) * S(m/8) + 2^m] + 2^m] + 2^m  ......(vi) //Level 3

So, if you follow the expressions you will find in each level a factor of (2^m) is added and so (2^(m/(2^i))) is multiplied to S(m/(2^i)). 
Note: You can verify it by comparing equation (ii) and equation (v) or equation (v) and equation (vi).
So it turns out,
 S(m)=[(2^(m/(2^1))*2^(m/(2^2))*2^(m/(2^3))*....*2^(m/(2^i)))* S(m/(2^i))] 

         +[2^m + 2^m + ..... i terms]

Note: You may directly reach to the above relation just after equation (ii) or (iii) depending on your expertise.
Now, if you follow the first part in [ ] you can make it, 
  2^((m/2)[1+(1/2)+(1/4)+...+(1/(2^(i-1))])  .....(vii)

The part in [ ] in the above line is a GP series with first term a=1 and r=1/2 with i terms. As this is a monotonically increasing series, if we make it for infinite terms, still it holds the upper bound.
Therefore, the sum of the series ie. the section inside [ ] has become,
 1/(1-(1/2)) =2

So now putting the value in equation (vii), we get,
 2^((m/2)*2) =2^m

Therefore,
 S(m) <= 2^m * S(m/(2^i) + i * 2^m  //As we took the series sum for infinite terms

No if we consider S(1) as the base case and S(1)=1, then 
 m/(2^i) =1; and i=lg m; ..............(viii)

put the value of i in the equation (viii) to get
 S(m) <= 2^m * S(1) + lg m * 2^m

      <= 2^m + lg m * 2^m     //As, S(1)=1

No return to T(n) by replacing the variables.
 S(lg n) <= n + lg (lg n) * n

 T(n) <= n + n * lg (lg n) 

Therefore, 
 T(n) = O(n lg(lg n))

Now, for the approximation we made for the GP series in equation (vii) is not relevant for calculation that  lower bound as,
 n = O(n lg(lg n))

So, we can conclude,
 T(n) = 0(n lg(lg n)) //"Theta of n lg of lg of n"

