# 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).

– Em.
Jan 16 '16 at 20:52
• It says it doesn't apply to $T(n) = 2T(n/2) + n \log^2 n.$ and yet the answer does appear to be $\Theta(n \log^3 n)$
– AJJ
Jan 16 '16 at 20:55

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

• So basically the quotient of the larger over the smaller function needs to be greater than $n^k$ for $k>0$, is that right?
– AJJ
Jan 16 '16 at 21:04
• It needs to fall between two (generalized) polynomials. I added a formal statement. Notably fractional exponents are allowed (and generally count as polynomials for complexity theory) Jan 16 '16 at 21:06
• So I suppose it is easy to just have $n^{\text{huge number}}$ for the upper bound in practice, hard part is seeing if lower bound exists. How do I know that $n / \log(n) \geq n^{1/3}$?
– AJJ
Jan 16 '16 at 21:07
• That can be rearranged to give $n^{2/3}\geq\log(n)$ which can be shown a number of ways. It is not too hard to show that $\log(n)\leq n^c$ for every $c>0$ (asymptotically) Jan 16 '16 at 21:10
• If I have $n / \log(n) \geq n^k$ then $n/n^k \geq \log(n)$ implies $n^{1-k} \geq \log(n)$, so I suppose this means $1-k>0$ is sufficient, or $1>k$? Any $k$ less than $1$ will satisfy the lower bound?
– AJJ
Jan 16 '16 at 21:12