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!

  • $\begingroup$ Apply (equivalent) regularity condition as $a\cdot f(n/b) \leq f(n)$ and retry. $\endgroup$ – Shreesh Sep 9 '20 at 3:40
  • $\begingroup$ Welcome to COMPUTERSCIENCE @SE. I thing you did a good job pinpointing just exactly one position on the way to the solution. $\endgroup$ – greybeard Sep 10 '20 at 7:32

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.

  • $\begingroup$ 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$ $\endgroup$ – dairyknight86 Sep 9 '20 at 13:28
  • $\begingroup$ Since $a = 9$ and $b = 3$, $af(n/b) = 9f(n/3) = 9(n/3)^3$. $\endgroup$ – Yuval Filmus Sep 9 '20 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.