How to Solve the following Recurrence Equation?
Regarding the master method, I don't quite understand why you got stuck. You had to show that the function $f(n) = 2^n$ satisfies $f(n/2) \leq (1-\epsilon) f(n)$ for some $\epsilon &gt; 0$ and large enough $n$. You showed this using some complicated calculation. So the condition is satisfied, and the method applies, giving the answer $T(2^m) = \Theta(f(m)) = \Theta(2^m)$. A more elementary way to check the condition is to notice that when $n \geq 2$, 
$$
2^{n/2} \leq 2^{n-1} = \frac{1}{2} \cdot 2^n.
$$

Regarding substitution, clearly $f(n) \geq n + c$. In the other direction, when $n \geq M$ we have $\sqrt{n} \leq n/\sqrt{n} \leq n/\sqrt{M}$, $\sqrt[4]{n} \leq \sqrt{n}/\sqrt{M} \leq n/M$, and so on. Therefore when $n^{1/2^{k+1}} \geq M$,
$$
\begin{align*}
f(n) &amp;= n + c + \sqrt{n} + c + \cdots + n^{1/2^k} + c + f(n^{1/2^{k+1}}) \\ &amp;\leq n + \frac{n}{\sqrt{M}} + \cdots + \frac{n}{\sqrt{M}^k} + (k+1) c + f(n^{1/2^{k+1}}) \\ &amp;\leq
n \sum_{t=0}^\infty \frac{1}{\sqrt{M}^t} + (k+1)c + f(n^{1/2^{k+1}}) \\ &amp;=
\frac{1}{1-1/\sqrt{M}} n + (k+1)c + f(n^{1/2^{k+1}}).
\end{align*}
$$
Choosing $k$ so that $n^{1/2^{k+1}} \approx M$, we deduce that
$$
f(n) \leq \frac{1}{1-1/\sqrt{M}} n + O(c\log\log n),
$$
where the hidden constant depends on $M$. Choosing an arbitrary $M$, we get $f(n) = O(n)$. This implies that
$$
f(n) = n + c + f(\sqrt{n}) = n + O(\sqrt{n}).
$$
Combining this with the lower bound, we have
$$
n + c \leq f(n) \leq n + O(\sqrt{n}).
$$
This is a much better estimate than the one we got using the master theorem.