What is the difference between x being asymptotically larger than y and x being polynomially larger than y?
asymptotically larger vs polynomially larger
2 Answers
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.
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.
-
0I 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. – 2017-08-30