5
$\begingroup$

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

2 Answers 2

5

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
    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)$.2017-03-13
  • 0
    Some others who feel the same way (from a quick google): [(1)](http://math.stackexchange.com/a/1614862/5531), [(2)](http://softwareengineering.stackexchange.com/a/158770), [(3)](https://books.google.be/books?id=aefUBQAAQBAJ&pg=PA95&lpg=PA95&dq=polynomially+larger&source=bl&ots=dMawRrVJc1&sig=o6k9pPXXmzm-hoU821jDP8NJWFQ&hl=en&sa=X&ved=0ahUKEwiEqIWeo9PSAhXHvRoKHYOcBs0Q6AEIUjAJ#v=onepage&q=polynomially%20larger&f=false), [(4)](http://gateoverflow.in/74641/difference-between-asymptotically-large-polynomially-large).2017-03-13
  • 0
    I can assure you that in theoretical computer science this usage does occur. I didn't make it up.2017-08-30
  • 0
    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.2017-09-01
  • 0
    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.2017-09-01
3

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.

  • 0
    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.2017-08-30