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?


1 Answer 1


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

  • $\begingroup$ When you say epsilon > 0 you mean real numbers or integers. As we talk about polynomials n^k, k must be an integer. $\endgroup$
    – Atinesh
    Sep 13, 2015 at 13:00
  • $\begingroup$ @Atinesh Epsilon is real, and in this context $n^k$ is polynomial for all real $k>0$. $\endgroup$ Sep 13, 2015 at 13:50
  • $\begingroup$ 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. $\endgroup$
    – Atinesh
    Sep 13, 2015 at 15:19
  • $\begingroup$ @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}$. $\endgroup$
    – jadhachem
    Sep 13, 2015 at 17:01
  • $\begingroup$ Ok So we consider n^k where k=real to be a polynomial in this context. $\endgroup$
    – Atinesh
    Sep 13, 2015 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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