3
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ No. It’s a polynomial speedup. $\endgroup$ – Yuval Filmus Jan 23 at 1:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Rascalniikov Jan 23 at 8:27
  • 1
    $\begingroup$ 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? $\endgroup$ – Rascalniikov Jan 23 at 8:36
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Yuval Filmus Jan 23 at 15:01
  • $\begingroup$ Can you add more explanation on why you think n log n is an exponential speedup over n^2 $\endgroup$ – Ṃųỻịgǻňạcểơửṩ Jan 23 at 22:44
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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}$ $\endgroup$ – Rascalniikov Jan 23 at 19:41
  • $\begingroup$ @Rascalniikov Thank you very much ! I sent a suggested edit to you, please accept it, or improve the edit to make further explanation. $\endgroup$ – Ṃųỻịgǻňạcểơửṩ Jan 23 at 19:54

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.