COMP 2711 Ex 20

1

$$T(n)=\{\begin{array}{ll}3T\left(\frac{n}{3}\right)+n& \text{if }n\ge 3\\ 1& \text{if }n<3\end{array}$$ $$\begin{array}{rl}T(n)& =3T\left(\frac{n}{3}\right)+n\\ & =3\left(3T\left(\frac{n}{3^2}\right)+\frac{n}{3}\right)+n\\ & =3^{2}T\left(\frac{n}{3^2}\right)+2n\\ & =3^2\left(3T\left(\frac{n}{3^3}\right)+\frac{n}{3^2}\right)+2n\\ & =3^{3}T\left(\frac{n}{3^3}\right)+3n\\ & ⋮\\ & =3^{{\log }_3(n)}T\left(\frac{n}{3^{{\log }_3(n)}}\right)+{\log }_3(n)\cdot n\\ & =n+n{\log }_3(n)\end{array}$$

The time complexity would be $O(n\log n)$