# Tag Info

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