0
$\begingroup$

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

$\endgroup$
2
1
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ Thank you @zkutch for this answer, but how can we express it in terms of Θ or O notations? $\endgroup$ – Rako Oct 15 '20 at 23:15
  • $\begingroup$ Of course, but before you should finish sum in right side - it is geometrical progression - can you do it? $\endgroup$ – zkutch Oct 16 '20 at 0:38
  • $\begingroup$ Here, a = 3, b=3, d = ½, and f(n) = √n , by comparing n^(log_b a)=n^(log_3 3)= n^1 ≠f(n) $\endgroup$ – Rako Oct 16 '20 at 0:47
  • $\begingroup$ @Rako. Finished it up to big-$O$. $\endgroup$ – zkutch Oct 16 '20 at 1:05
  • $\begingroup$ Looks like you dropped the 3 in front of T(n/3) $\endgroup$ – Bobby Durrett Oct 16 '20 at 1:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.