What is the difference between x being asymptotically larger than y and x being polynomially larger than y?


I don't agree with the definition of polynomially larger in the other answer, so here's the one I see used:

"Polynomially larger" means that the ratio of the functions falls between two polynomials, asymptotically. Specifically, $f(n)$ is polynomially greater than $g(n)$ if and only if there exist generalized polynomials (fractional exponents are allowed) $p(n),q(n)$ such that the following inequality holds asymptotically: $$p(n)\leq \frac{f(n)}{g(n)}\leq q(n)$$

This is more strict than merely asymptotically larger, and gives limits on how much faster the function can grow. For example, $n$ is not polynomially larger than $\frac{n}{\ln(n)}$ because the rate of growth is wrong. To see this, notice that there's no polynomial $p$ such that $$p(n)\leq\frac{n}{\frac{n}{\ln(n)}}=\ln(n)$$ holds asymptotically.

Another example of this is $e^n$, which is not polynomially larger than $n^k$ for any $k$. In both of these examples, the correct interpertation is that the function is asymptotically larger, but not polynomially so on the grounds of growing too quickly compared to $f(n)=n^k$ for the gap to be characterized as "polynomial." $e^n$ is exponentially larger than $n^k$, where "exponentially larger" is defined similarly to "polynomially larger" except using exponentials instead of polynomials.

  • $\begingroup$ I don't think that there is a standard definition of polynomial larger that is used in all areas of mathematics. You've seen your definition, and I've seen mine. None of them is "wrong" - it depends on the context. $\endgroup$ Aug 30 '17 at 20:51

Here's one possible interpretation, in common use in theoretical computer science. For a different interpretation, see the other answer.

We say that $x$ is asymptotically larger than $y$ if $\lim_{n \rightarrow \infty} x(n)/y(n) = \infty$. We write it $x \gg y$ or $y \ll x$ or $x = \omega(y)$ (rarely) or $y = o(x)$.

We say that $x$ is (at most) polynomially larger than $y$ if there is some $d$ such that $x = O(y^d)$, that is $\lim_{n \rightarrow \infty} x(n)/y(n)^d < \infty$, in other words there is some constant $C$ such that $x(n) \leq Cy(n)^d$.

Note that there is a very confusing semantic difference: the first notion is "strict" (like $>$), the second notion is "lax" (like $\leq$).

It's possible that different areas of mathematics understand these notions slightly differently.

  • 1
    $\begingroup$ That's not the common meaning of "polynomially larger". The statement "x is at most polynomially larger than y" means that $x(n)/y(n) = O(n^m)$ for some $m > 0$. I would not say that $4^n$ is "polynomially larger" than $2^n$, like your definition would allow. I would instead say that $4^n$ is exponentially larger than $2^n$, since $4^n/2^n = \Theta(2^n)$. $\endgroup$ Mar 13 '17 at 10:34
  • $\begingroup$ Some others who feel the same way (from a quick google): (1), (2), (3), (4). $\endgroup$ Mar 13 '17 at 10:35
  • $\begingroup$ I can assure you that in theoretical computer science this usage does occur. I didn't make it up. $\endgroup$ Aug 30 '17 at 20:50
  • $\begingroup$ I can't open that file, but I suppose it would be best to amend your answer to indicate that your "we" refers to theoretical computer scientists. $\endgroup$ Sep 1 '17 at 13:21
  • $\begingroup$ I'm not sure this usage is limited to theoretical computer scientists. Also, I don't see the other answer explaining which community its definition refers to. $\endgroup$ Sep 1 '17 at 13:54

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.