Applying Case 3 of Master Theorem to $T(n) = 9T(n/3) + n^3$

Question

Given $T(n) = 9T(n/3) + n^3$,

I know that $a =9$, $b=3$, and $f(n) = n^3$

and $n^{\log_{3}9} = n^2$

thus Case 3 applies: $n^{\log_{b}a} < f(n)$, $n^2 < n^3$.

Can someone explain how to apply the regularity condition and how to check the regularity condition?

$af(n/b) \le cf(n)$ where $c < 1$

I appreciate your help!

Answer 1

Your statement of the regularity condition has a typo: it suffices to show that there exists a constant $c < 1$ such that for large enough $n$, $$ af(n/b) \leq cf(n). $$

Substituting $a,b,f$, we have to show that for some constant $c < 1$, $$ 9(n/3)^3 \le c n^3. $$ You take it from here.