0

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?

prcssngnr
  • 1,191
xx33xx44
  • 19
  • 3
  • 1
    $T(n/3) = 2T(n/9) + 3(n/3)^2=2T(n/9) + n^2/3$ – Robert Z May 30 '23 at 15:13
  • Very similar to this question – prcssngnr May 30 '23 at 15:36
  • Okay, thank you, maybe I´m very stupid but then T(n) = 2 * (2* T(n/3/3) + n^2/3) + 3 n^2 = 4T(n/9) + 11/3(n^2). Insert again: T(n) = 4 * (2T(n/9/3) + ((3n^2)/9)) + 11/3n^2 = 8T(n/27) + 5x^2. is that right – xx33xx44 May 30 '23 at 15:44
  • From a quick look the computations in your last comment are correct. So if you see the pattern you could use that to come up with a solution. I provided an answer which follows the same reasoning you were following. – prcssngnr May 30 '23 at 18:00

1 Answers1

1

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.

prcssngnr
  • 1,191