3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\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 '15 at 13:00
  • $\begingroup$ @Atinesh Epsilon is real, and in this context $n^k$ is polynomial for all real $k>0$. $\endgroup$ – Yuval Filmus Sep 13 '15 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 '15 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 '15 at 17:01
  • $\begingroup$ Ok So we consider n^k where k=real to be a polynomial in this context. $\endgroup$ – Atinesh Sep 13 '15 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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