Is O(n log n) exponential speedup over O(n^2)?

Question

I would like to know if $O(n \log n)$ is an exponential speedup over $O(n^2)$?

Answer 1

$O(n \log n)$ is a polynomial speedup over $O(n^2)$, in particular almost a quadratic speedup. $O(n \log n)$ is big-O of $O(n^k$) for all $k > 1$. Its runtime is therefore between linear and any powerfunction whose exponent is strictly greater than 1.

Let $f(n)=n \log n$. Raise it to a power of some value slightly less than 2 to approximate the original runtime. We conclude $f(n) \approx n^{2-\varepsilon} (\log n)^{2-\varepsilon}$ and in $O(n^2)$. If we square $f(n)$, we have $n^2 (\log n)^2$, slightly less efficient than the original $n^2$, hence it is basically a quadratic speedup.

Instead, $O(\log n^2) = O(\log n)$ is an exponential speedup over $O(n^2)$. If $g(n) = 2\log(n)$, then $e^{g(n)} = n^2$.