Solve the recurrence equation: $T(n) = 2T(n/3) + 3 n^2$. Assume $T(0) = T(1) = O(1)$. Use the substitution and pattern recognition method.
My idea:
$$T(n/3) = 2T(n/9) + n^2$$
Insert:
$$T(n) = 2 (2T(n/3/3) + n^2) + 3 n^2 = 4T(n/9) + 5(n^2)$$
Insert again:
$$T(n) = 4 (2T(n/9/3) + ((3n^2)/9)) + 5n^2 = 8T(n/27) + (19/3)^2$$
The term with n^2 makes little sense now. Where is the error?
The approach followed here is the same as followed here. We will expand the recurrence, which I assume is what you mean by pattern recognition, and then generalise. The first iteration of the expansion is:
$$T \left( n \right) = 2 T \left( \frac{n}{3} \right) + 3n^2$$
The next one is:
$$T \left( n \right) = 3n^2 + 2 \cdot 3 \left( \frac{n}{3} \right)^2 + 2^2 T \left( \frac{n}{3^2} \right)$$
And after one more we get:
$$T \left( n \right) = 3n^2 + 2 \cdot 3 \left( \frac{n}{3} \right)^2 + 2^2 \cdot 3 \left( \frac{n}{3^2} \right) + 2^3 T \left( \frac{n}{3^3} \right)$$
And now we generalise to:
$$ T \left( n \right) = 2^{\log_3 n} + \sum_{i = 0}^{-1 + \log_3 n} 3 \cdot 2^i \left( \frac{n}{3^i} \right)^2$$
$$ T \left( n \right) = 2^{\log_3 n} + 3n^2 \sum_{i = 0}^{-1 + \log_3 n} \left( \frac{2}{9} \right)^i$$
Computing the geometric series we get:
$$T\left( n \right) = \frac{27}{7} n^2 - \frac{20}{7} 2^{\log_3 n} $$
We can verify the result using the substitution method. We substitute above into the recurrence:
$$T \left( n \right) = 3n^2 + 2 T \left( \frac{n}{3} \right)$$
$$T \left( n \right) = 3n^2 + 2 \left( \frac{27}{7} \left( \frac{n}{3} \right)^2 - \frac{20}{7} 2^{\log_3 \frac{n}{3}} \right)$$
$$T \left( n \right) = 3n^2 + \frac{6}{7} n^2 - \frac{40}{7 \cdot 2} 2^{\log_3 n}$$
$$T \left( n \right) = \frac{27}{7} n^2 - \frac{20}{7} 2^{\log_3 n}$$
And so we conclude the result is valid.