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} < 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$$

• Apply (equivalent) regularity condition as $a\cdot f(n/b) \leq f(n)$ and retry. – Shreesh Sep 9 '20 at 3:40
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.
• How did you transform $af(n/b) \le cf(n)$ to $9(n/3)^3 \le cfn^3$> I see the $cf(n)$ but not $9(n/3)^3$ – dairyknight86 Sep 9 '20 at 13:28
• Since $a = 9$ and $b = 3$, $af(n/b) = 9f(n/3) = 9(n/3)^3$. – Yuval Filmus Sep 9 '20 at 14:32