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

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

• No. It’s a polynomial speedup. Jan 23 '20 at 1:14
• I suppose you are correct, the first term is dominated by a linear term, while the log n term is negligible, so the speedup for large n looks approximately like n^2 vs Cn for some constant C, but I'd like an answer in terms of formal definitions and workings. Jan 23 '20 at 8:27
• How do I show that this is a polynomial speedup formally? Is it precisely a polynomial speedup or is there a more accurate term to describe it, like I don't know, subpolynomial? Jan 23 '20 at 8:36
• You improved $f(n)$ to roughly $\sqrt{f(n)}$. This is a polynomial improvement. An exponential improvement would have been something like $\log f(n)$. Jan 23 '20 at 15:01
• Can you add more explanation on why you think n log n is an exponential speedup over n^2 Jan 23 '20 at 22:44

$$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$$.
• I see, it is an almost quadratic speedup in the sense that the original function raised to any power less than 2 will be in $O(n^2),$ in fact $o(n^2)$. That's because for $n$ large enough, $(\log n )/ n^k < \epsilon$, $k>0$, since $n < e^{\epsilon n^k}$ for n large enough. That's because, there an integer N, $kN > 1$, so that the term in the taylor expansion of the exponential term has $\epsilon^N n^{kN}/N! > n$ for $n^{kN-1} > N!/\epsilon^{N}$ Jan 23 '20 at 19:41