Solve the recurrence relation:$ T(n) = \sqrt{n} T \left(\sqrt n \right) + n$

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}})$

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$$

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)$$