8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Possibly relevant. Link 1. Link 2. Link 3.. $\endgroup$ – Em. Jan 16 '16 at 20:52
  • $\begingroup$ 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)$ $\endgroup$ – AJJ Jan 16 '16 at 20:55
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So basically the quotient of the larger over the smaller function needs to be greater than $n^k$ for $k>0$, is that right? $\endgroup$ – AJJ Jan 16 '16 at 21:04
  • $\begingroup$ 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) $\endgroup$ – Stella Biderman Jan 16 '16 at 21:06
  • 1
    $\begingroup$ 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}$? $\endgroup$ – AJJ Jan 16 '16 at 21:07
  • 1
    $\begingroup$ 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) $\endgroup$ – Stella Biderman Jan 16 '16 at 21:10
  • $\begingroup$ 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? $\endgroup$ – AJJ Jan 16 '16 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.