I'm reading CLRS Section-4.5: The Master method for solving recurrences. There is a line saying
$f(n)$ must be polynomially smaller than $n^{\log_b a}$.
What is meant by polynomially smaller? Can anybody explain it to me with an example?
In this context, the line means $f(n) = O(n^{\log_b a - \epsilon})$ for some $\epsilon > 0$.
More generally, there are a few possible interpretations. Under one interpretation, $f(n)$ is at least polynomially smaller than $g(n)$ if $f(n) = O(g(n)/n^\epsilon)$ for some $\epsilon > 0$; and $f(n)$ is at most polynomially smaller than $g(n)$ if $f(n) = \Omega(g(n)/n^\epsilon)$ for some $\epsilon > 0$.
A different interpretation has $f(n)$ at least polynomially smaller than $g(n)$ if $f(n) \leq g(n)^{1-\epsilon}$ for some $\epsilon > 0$, and at most polynomially smaller than $g(n)$ if $f(n) \geq g(n)^\epsilon$ for some $\epsilon > 0$.
epsilon > 0
you mean real numbers or integers. As we talk about polynomials n^k, k must be an integer.
$\endgroup$
k
is an integer. how k can be real.
$\endgroup$