Solve recurrence $T(n) = T(\frac34n) + \sqrt n$

Question

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.

Answer 1

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.

Answer 2

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