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.
 A: An elementary way which doesn't use the Master Theorem could be:
$\begin{align*}
T(n) = T\left(\frac{3}{4} n\right) + \sqrt{n} \iff T(4n^2) = T(3n^2) + 2n
\end{align*}$
Thus, let us assume that $T(n) = C n^{\alpha}$ for some $C, \alpha$, is solution for the previous relation.
Then: $C(4^{\alpha} - 3^{\alpha})n^{2\alpha} = 2n$.
Then: $C(4^{\alpha} - 3^{\alpha})n^{2\alpha - 1} = 2$.
Now, this is true for all $n \in \mathbb{N}$, so $\alpha = \dfrac{1}{2}$ in order for $n^{2\alpha - 1} = 1$.
Then: $C = \dfrac{2}{\sqrt{4} - \sqrt{3}}$.
Now: $T(n) = \dfrac{2}{\sqrt{4} - \sqrt{3}} \sqrt{n}$.
Let us verify if $T$ is indeed a solution of your relation.
$\begin{align*}
T\left(\dfrac{3}{4} n\right) + \sqrt{n} & = C\sqrt{\dfrac{3}{4} n} + \sqrt{n} \\
& = \left[\dfrac{C}{2}\sqrt{3} + 1\right] \sqrt{n} \\
& = \left[\dfrac{1}{\sqrt{\frac{4}{3}} - 1} + 1\right] \sqrt{n} \\
& = \dfrac{2}{\sqrt{4} - \sqrt{3}} \sqrt{n} \\
& = C \sqrt{n} \\
& = T(n)
\end{align*}$
Which is coherent with the Master Theorem.
A: 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$.
