Solving the recurrence formula $T(n) = 3T(n/2)+n^2$
First of all, your recurrence is defined only when $n$ is a power of 2, so let us assume that $n = 2^m$. Expanding the recurrence, we get
\begin{align}
T(n) &amp;= n^2 + 3T(n/2) \\ &amp;=
n^2 + 3(n/2)^2 + 9T(n/4) \\ &amp;=
n^2 + 3(n/2)^2 + 9(n/4)^2 + 27T(n/8) \\ &amp;= \cdots \\ &amp;=
n^2 + 3(n/2)^2 + 9(n/4)^2 + \cdots + 3^{m-1} (n/2^{m-1})^2 + 3^m T(n/2^m) \\ &amp;=
n^2 + 3(n/2)^2 + 9(n/4)^2 + \cdots + 3^{m-1} (n/2^{m-1})^2 \\ &amp;=
n^2 \left[1 + \frac{3}{4} + \left(\frac{3}{4}\right)^2 + \cdots + \left(\frac{3}{4}\right)^{m-1} \right] \\ &amp;=
\frac{1-(3/4)^m}{1-(3/4)} n^2 \\ &amp;=
4n^2 - 4 \cdot 3^m \\ &amp;=
4n^2 - 4n^{\log_2 3}.
\end{align}