Note que podemos resolver esse problema facilmente usando uma árvore recursiva:
Raiz da árvore: \(n^2\)
Primeira geração: \(T(n/4)=(n/4)^2\) e \(T(n/2)=(n/2)^2\) dando um total de \(\frac{5}{16}n^2\).
Segunda geração: \(T(n/16)=(n/16)^2\), \(T(n/8)=(n/8)^2\), \(T(n/8)=(n/8)^2\), \(T(n/4)=(n/4)^2\) dando um total de \(\frac{25}{256}n^2\).
Logo, o custo total é
\((1+ 5/16 + 25/256 + \cdots)n^2 =\frac{n^2}{1-5/16}\in O(n^2)\)