If you want to make money online : Register now

# What is meant by polynomially smaller

, ,
Problem Detail:

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?

#### Answered By : Yuval Filmus

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