Consider the recurrence
$\qquad\displaystyle T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + c\,n$
for $n \gt 2$ with some positive constant $c$, and $T(2) = 1$.
I know the Master theorem for solving recurrences, but I'm not sure as to how we could solve this relation using it. How do you approach the square root parameter?
We will use Raphael's suggestion and unfold the recurrence. In the following, all logarithms are base 2. We get
$$ \begin{align*} T(n) &= n^{1/2} T(n^{1/2}) + cn \\ &= n^{3/4} T(n^{1/4}) + n^{1/2} c n^{1/2} + cn\\ &= n^{7/8} T(n^{1/8}) + n^{3/4} c n^{1/4} + 2cn\\ &= n^{15/16} T(n^{1/16}) + n^{7/8} c n^{1/8} + 3cn \\ & \ldots \\ &= \frac{n}{2} T(2) + c n \beta(n) \end{align*}. $$ where $\beta(n)$ is how many times you have to take the square root to start with n, and reach 2. It turns out that $\beta(n) = \log \log n$. How can you see that? Consider: $$ \begin{align*} n &= 2^{\log n}\\ n^{1/2} &= 2^{\frac{1}{2} \log n} \\ n^{1/4} &= 2^{\frac{1}{4} \log n} \\ \ldots \end{align*} $$ So the number of times you need to take the square root in order to reach 2 is the solution to $\frac{1}{2^t} \log n \approx 1$, which is $\log \log n$. So the solution to the recursion is $c n \log \log n + \frac{1}{2}n$. To make this absolutely rigorous, we should use the substitution method and be very careful about how things get rounded off. When I have time, I will try to add this calculation to my answer.
In your comment you mentioned that you tried substitution but got stuck. Here's a derivation that works. The motivation is that we'd like to get rid of the $\sqrt{n}$ multiplier on the right hand side, leaving us with something that looks like $U(n) = U(\sqrt{n}) + something$. In this case, things work out very nicely:
$$\begin{align} T(n) &= \sqrt{n}\ T(\sqrt{n}) + n & \text{so, dividing by $n$ we get}\\ \frac{T(n)}{n} &= \frac{T(\sqrt{n})}{\sqrt{n}} + 1 &\text{and letting $n = 2^m$ we have}\\ \frac{T(2^m)}{2^m} &= \frac{T(2^{m/2})}{2^{m/2}} + 1 \end{align}$$ Now let's simplify things even further, by changing to logs (since $\lg \sqrt{n} = (1/2)\lg{n}$). Let $$\begin{align} S(m) &= \frac{T(2^m)}{2^m} & \text{so our original recurrence becomes}\\ S(m) &= S(m/2)+1 \end{align}$$ Aha! This is a well-known recurrence with solution $$ S(m)=\Theta(\lg m) $$ Returning to $T(\,)$, we then have, with $n=2^m$ (and so $m=\lg n$), $$ \frac{T(n)}{n} = \Theta(\lg\,\lg n) $$ So $T(n) =\Theta(n\,\lg\,\lg n)$.
If you write $m=\log n \space$ you have $T(m) = {m \over 2}\cdot T({m\over 2}) + c\cdot 2^m\space$.
Now you know the recursion tree has hight of order $O(\log m)$, and again it's not hard to see it's $O(2^m)\space$ in each level, so total running time is in: $O((\log m) \cdot 2^m)\space$, which concludes $O(n \cdot \log \log n)\space$ for $n$.
In all when you see $\sqrt n $ or $n^{a \over b}, a<b \space$, is good to check logarithm.
P.S: Sure proof should include more details by I skipped them.
Let's follow Raphael's suggestion, for $n = 2^{2^k}$: $$ \begin{align*} T(n) = T(2^{2^k}) &= 2^{2^{k-1}} T(2^{2^{k-1}}) + c2^{2^k} \\ &= 2^{2^{k-1}+2^{k-2}} T(2^{2^{k-2}}) + c(2^{2^k} + 2^{2^k}) \\ &= \cdots \\ &= 2^{2^{k-1}+2^{k-2}+\cdots+2^0} T(2^{2^0}) + c(2^{2^k} + 2^{2^k} + \cdots + 2^{2^k}) \\ &= 2^{2^k-1} + ck2^{2^k} \\ &= (c\log\log n + 1/2)n. \end{align*} $$
Edit: Thanks Peter Shor for the correction!
Unravel the recurrence once as follows: \begin{align} T(n) &=& \sqrt{n}~ T(\sqrt{n}) + n \\ &=& n^{1/2} \big ( n^{1/4} ~ T(n^{1/4}) + n^{1/2}\big) + n \\ &=& n^{1-1/4}~ T(n^{1/4}) + 2n. \end{align}
Continuing the unraveling for $k$ steps, we have that: \begin{align} \label{eqn:unrav} T(n) &=& n^{1-1/2^k} T(n^{1/2^k}) + kn. \end{align}
These steps will continue until the base case of $n^{1/2^k} = 2$. Solving for $k$ we have:
\begin{align} &&n^{1/2^k} = 2 \\ &\implies& \log n= 2^k \\ &\implies& k= \log \log n. \label{eqn:ksol} \end{align}
Substituting $k=\log \log n$ into the unraveled recurrence, we have \begin{align} T(n) = \frac{n}{2} T(2) + n \log \log n. \end{align}
