# asymptotically larger vs polynomially larger

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.

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

• 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)$. Mar 13 '17 at 10:34
• Some others who feel the same way (from a quick google): (1), (2), (3), (4). Mar 13 '17 at 10:35
• I can assure you that in theoretical computer science this usage does occur. I didn't make it up. Aug 30 '17 at 20:50
• 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. Sep 1 '17 at 13:21
• 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. Sep 1 '17 at 13:54