Applying Case 3 of Master Theorem to $T(n) = 9T(n/3) + n^3$ 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} &lt; f(n)$, $n^2 &lt; 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 &lt; 1$
I appreciate your help!
Your statement of the regularity condition has a typo: it suffices to show that there exists a constant $c &lt; 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 &lt; 1$,
$$
9(n/3)^3 \le c n^3.
$$
You take it from here.