Solving $T(n) = 4T(n/2) + n^3$ with substituton method I am trying to solve the following recurrence $T(n) = 4T(n/2) + n^3$ with substitution method. My guess is $T(n) = \Theta (n^3)$ (I used master theorem) and I tried to show that $T(n) \leq cn^3$. But, when I substitute I got $T(n) \leq c \frac{n^3}{2} + n^3$ and that's it not the exact form of the guess, so it doesn't work. How can I solve this recurrence?
Your guess works: if $T(n) \le c n^3$ and $c \ge 2$ then
$$
T(n) = 4c \frac{n^3}{8} + n^3 = \frac{c}{2} n^3 + n^3 = cn^3 \left(\frac{1}{2}+\frac{1}{c} \right) \le cn^3.
$$