How to solve $T(n) = 27T(n/9) + n^3$ with substitution method

I'm trying to bound this recurrence with the substitution method. My guess is $$O(n^3)$$. These are some steps: $$T(n) \leq cn^3 \\ T(n) \leq 27cn^3+n^3$$ How can I continue?

• Do you realise that $\frac{27n}{9} = 3n$? Commented Nov 26, 2021 at 16:56
• This question makes no sense, the result will be a negative number. Since the RHS has $T(3n)$ and $3n>n$, you will need to rearrange in order to substitute correctly. After the rearranging it will be clear why the result is negative. Commented Nov 26, 2021 at 17:03

I am assuming that the recurrence relation you are trying to solve is: $$T(n) = 27T(n /9) + n^3$$
Using the substitution method, you can prove that for any $$k \leqslant \log_3 n$$: $$T(n) = 3^{3k}T\left(\frac{n}{3^{2k}}\right) + n^3\sum\limits_{i=0}^{k-1} \frac{1}{27^i}$$
For $$k = \log_3n$$, we get $$T(n) \leqslant n^3T(1) + n^3\sum\limits_{i=0}^{+\infty}\frac{1}{27^i}=n^3(T(1) + \frac{27}{26})$$.
Since clearly $$T(n) \geqslant n^3$$, we conclude that $$T(n) = \Theta(n^3)$$.