Meaning of "polynomially larger"

For example

Is $n$ polynomially larger than $\frac{n}{\log n}$? Than $n \log n$?

Is $n^2$ polynomially larger than $\frac{n}{\log n}$? Than $n \log n$?

I am trying to understand the difference because apparently the first line isn't, but the second is (Master Theorem).

Solution 1:

"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)$$

For the first problem, we have the ratio is equal to $\log(n)$. It is not the case that there exist polynomials $p(n),q(n)$ such that $p(n)\leq \log(n)\leq q(n)$ asymptotically, because no polynomial is a lower bound for $\log(n)$. Thus it is not polynomially bounded. $n\log(n)$ is the same (even the same quotient if taken in the other order).

For the second problem, we have the ratio is equal to $n\log(n)$. It is the case that $n\leq n\log(n)\leq n^2$ asymptotically, so it is polynomially bounded and therefore $n^2$ is polynomially larger. $\frac{n^2}{n\log(n)}=\frac{n}{\log(n)}$, and we have that (asymptotically) $$n^\frac{1}{3}\leq \frac{n}{\log(n)}\leq n$$