How to solve the equation T(n) = 3T(n/3) + 3n

Question

Task: Solve the recurrence equation:

$$T(n) = 3T\left( \frac{n}{3} \right) + 3n$$

Assume $T(0) = T(1) = O(1)$. My approach is:

$$T\left( \frac{n}{3} \right) = 3T\left( \frac{n}{9} \right) + \left( \frac{3n}{3} \right) = 3T\left( \frac{n}{9} \right) + n$$

$$T\left( \frac{n}{9} \right) = 3T\left( \frac{n}{27} \right) + \left( \frac{3n}{9} \right) = 3T\left( \frac{n}{27} \right) + \left( \frac{n}{3} \right)$$

Thus:

$$T(n) = 3\left(3T\left( \frac{n}{9} \right) + n\right) + 3n = 9T\left( \frac{n}{9} \right) + 6n$$

$$T(n) = 9\left(3T\left( \frac{n}{27} \right) + n\right) + 3n = 27T\left( \frac{n}{27} \right) + 12n$$

I don't recognise the pattern from $3n$ to $6n$ and $12n$, then should $9n$ come out there. Can someone help me to find the mistake?

Answer 1

You were on the right track. We will complete the reasoning here. As you were doing we expand the recurrence. The first iteration being:

$$T\left(n\right) = 3n + 3 T \left( \frac{n}{3} \right)$$

The next one being:

$$T\left(n\right) = 3n + 3n + 3^2 T \left( \frac{n}{3^2} \right)$$

And after one more:

$$T\left(n\right) = 3n + 3n + 3n + 3^3 T \left( \frac{n}{3^3} \right)$$

The number of times $k$ required to divide $n$ by $3$ to get $n$ down to $O(1)$, i.e.: $n = 3^k$, is $\log_3 n$. Now we generalise to:

$$T \left( n \right) = 3n \log_3 n + n$$

We can verify the explicit form using the substitution method:

$$T\left(n\right) = 3n + 3 \left( 3 \frac{n}{3} \log_3 \frac{n}{3} + \frac{n}{3} \right)$$

$$T\left(n\right) = 3n \log_3 \frac{n}{3} + n + 3n$$

$$T\left(n\right) = 3n \log_3 n - 3n \log_3 3 + n + 3n$$

$$T\left(n\right) = 3n \log_3 n + n$$