# Solving $T(n) = 3T(\frac{n}{3})+\sqrt{n}$ using master method

How can I use the master's method in order to solve the recurrence formula $$T(n)=3T(\frac{n}{3})+\sqrt{n}$$ ?

Taking $$n=3^k$$ we have $$T(n) =3 T(n/3) + \sqrt{n} =3^2T\left(\frac{n}{3^2}\right) +3\sqrt{\frac{n}{3}}+ \sqrt{n} =\\ =3^3T\left(\frac{n}{3^3}\right) +3^2\sqrt{\frac{n}{3^2}}+3\sqrt{\frac{n}{3}}+ \sqrt{n} = \cdots=\\ =3^kT\left(\frac{n}{3^k}\right)+3^{k-1}\sqrt{\frac{n}{3^{k-1}}}+\cdots +3\sqrt{\frac{n}{3}}+ \sqrt{n} =\\ =3^kT(1)+\sqrt{n}\left( (\sqrt{3})^{k-1}+\cdots + \sqrt{3} +1\right) =\\ = 3^kT(1)+\sqrt{n}\frac{1-(\sqrt{3})^{k}}{1-\sqrt{3}}=\\ =\sqrt{n}T(1)+\sqrt{n}\frac{1-\sqrt{n}}{1-\sqrt{3}} \in O(n)$$
• @Rako. Finished it up to big-$O$. Oct 16 '20 at 1:05