# What is meant by polynomially smaller

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

• When you say epsilon > 0 you mean real numbers or integers. As we talk about polynomials n^k, k must be an integer. Sep 13 '15 at 13:00
• @Atinesh Epsilon is real, and in this context $n^k$ is polynomial for all real $k>0$. Sep 13 '15 at 13:50
• But that will contradict the definition of polynomials. n^k will be a polynomial only if k is an integer. how k can be real. Sep 13 '15 at 15:19
• @Atinesh In a CS context, "polynomial" isn't restricted to precisely $n^k$ for integer $k$. In fact, all of the following are "polynomial": $n^2+\sqrt{n}$, $n\log n$, $n^{1.432}$, etc. In the context of running time, it wouldn't make sense to include, for example, $n^2$ and $n^3$ in the same class but to exclude $n^{2.5}$. Sep 13 '15 at 17:01
• Ok So we consider n^k where k=real to be a polynomial in this context. Sep 13 '15 at 17:36