2
$\begingroup$

The Master method for solving recurrences of the kind $T(n) = aT(n/b) + f(n)$ has a third case, which requires a regularity condition to hold:

$$ af(n/b) \le cf(n) \qquad a \ge 1, b > 1, c < 1$$

This should imply that

$$ f(n) = \Omega(n^{\log_ba+\epsilon}) \text{ where } \epsilon > 0 .$$

However, I cannot prove it. I'm afraid it might be beyond the mathematical apparatus I currently command.

The only reasoning I come up with is to prove that if $f(n)$ is polynomial, then $g \ge \log_{b}a+\epsilon$, where $\epsilon > 0$. This is fairly easy if you substitute $n^{\log_{b}a+\epsilon}$ for $f(n)$ in the regularity condition, but I cannot find a way to generalize it. I'm don't feel it is the right direction either.

Any help would be greatly appreciated!

P.S.: This is exercise 4.6-3 from CLRS 3ed that I'm currently reading for fun.

$\endgroup$

1 Answer 1

3
$\begingroup$

The idea is probably that $f(bn)\geqslant\alpha f(n)$ with $\alpha=a/c\gt a$ hence $f(b^i)\geqslant\alpha^i f(1)$ for every $i\geqslant0$. If $n=b^i$, then $i=\log _bn$ hence $f(n)\geqslant\alpha^{\log _bn} f(1)$.

Finally, $\alpha^{\log _bn}=n^{\log_b\alpha}$ and $\log_b\alpha\gt\log_ba$ hence $\log_b\alpha=\log_ba+\epsilon$ with $\epsilon\gt0$.

$\endgroup$
1
  • $\begingroup$ Thank you for clarifying this! :) $\endgroup$ Commented Oct 2, 2013 at 7:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .