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