Solve recurrence $T(n) = T(\frac34n) + \sqrt n$ How can I solve the following recurrence relation?
$T(n) = T(\frac34n) + \sqrt n$
I have attempted to solve it with the substitution method.
I believe that the general pattern is $T(n) = T((\frac34)^kn) + n^{\frac1{2^k}}$,
but I cannot think of what method I need to follow to reach the closed form.

You can use the Master Theorem, for which $a=1$, $b=\frac{4}{3}$, and $d=\log_ba=0$.  Certainly $\sqrt{n}=\Omega(n^d)=\Omega(1)$.
If $\sqrt{n}$ satisfies the regularity condition, which it does(*), then the Master Theorem tells us that $T(n)=\Theta(\sqrt{n})$.

(*) The regularity condition is $\sqrt{\frac{3n}{4}}\le k \sqrt{n}$, for some $k<1$ and for all $n$ sufficiently large.  This is easily checked with $k=\sqrt{\frac{3}{4}}\approx 0.866<1$.
