1) a. \(T\left(n\right)\ =\ 3T\left(\frac{n}{4}\right)\ +\ \sqrt{n},\ T\left(1\right)\ =\ 1\)
Applying Master's Theorem, we get:
\(a\ =\ 3,\ b\ =4\)
\(\Rightarrow n^{\log_34}\ and\ f\left(n\right)=\sqrt{n}\)
\(\log_34\ \approx0.79\ \Rightarrow n^{0.79}>\ f\left(n\right)\)
\(T\left(n\right)\ =\ \theta\left(n^{0.79}\right);\ \ f\left(n\right)\ is\ smaller\ by\ a\ factor\ of\ \epsilon\ \approx\ 0.3\)
b. \(T\left(n\right)=9T\left(\frac{n}{3}\right)+5n^2,\ T\left(1\right)\ =\ 1\)
Applying Master's Theorem, we get:
\(a=9,\ b=3\)
\(n^{\log_39}=n^2\)
\(f\left(n\right)=5n^2\)
\(\ \Rightarrow T\left(n\right)\ =\ \theta\left(n^2\log n\right)\) [case 2]
c. \(T\left(n\right)=T\left(\frac{n}{3}\right)+T\left(\frac{2n}{3}\right)+cn^2\)
After expanding the recursion tree, we can see the cost at \(i\) depth is \(c\left(\frac{4}{9}\right)^in^2\)