12
$\begingroup$

I know that $O(n^2\times \log(n))$ is greater than $O(n^2)$, but is $O(n^2\times \log(n))$ greater than $O(n^{2.5})$?

$\endgroup$
  • 2
    $\begingroup$ We have a reference question with plenty of material on this. Happy reading! $\endgroup$ – Raphael Nov 25 '19 at 21:22
16
$\begingroup$

In order to compare 2 complexities just calculate a limit of their ratios as below:

$\displaystyle\begin{align*} \lim_{n\to\infty}\frac{n^2log(n)}{n^2\sqrt{n}} &= \lim_{n\to\infty}\frac{log(n)}{\sqrt{n}} = \lim_{n\to\infty}\frac{log(\sqrt{n})^2}{\sqrt{n}} = \lim_{n\to\infty}\frac{2log(\sqrt{n})}{\sqrt{n}} \\ &\underset{\left| k = \sqrt{n} \right|}{=} \ \ \lim_{k\to\infty}\frac{2log{(k)}}{k} = 2\lim_{k\to\infty}\frac{log{(k)}}{k} \\ &\leq 2\lim_{k\to\infty}\frac{ln{(k)}}{k} \\ &\overset{\ast}{=} 2\lim_{k\to\infty}\frac{(ln{(k))'}}{k'} = 2\lim_{k\to\infty}\frac{\frac{1}{k}}{1} = 2\lim_{k\to\infty}\frac{1}{k} \\ &= 0 \end{align*}$

We use L'Hôpital's rule to simplify calculating a limit for $\frac{\ln(k)}{k}$ at *.

As you can see, $O(n^2\times\log(n))$ is lower than the other.

$\endgroup$
12
$\begingroup$

$O(n^2 \times \log(n))$ is greater than $O(n^2)$ but it is smaller than $O(n^{2 + \epsilon})$ for any $\epsilon > 0$, however small $\epsilon$ is (see here).

In particular, it is smaller than $O(n^{2.5})$. You're basically comparing the growth of $\log$ and square root.

$\endgroup$
5
$\begingroup$

As $n^{0.5}$ is always greater than $\log(n)$, $O(n^{2.5})= O(n^2 \times n^{0.5})$ is always bigger than $O(n^2 \times \log(n))$. Anyway, you should consider your real algorithm usage scenario to choose one which fits the best.

$\endgroup$
  • $\begingroup$ Yeah thank you, but sorry, i forgot parentheses on n^2*log(n), it's n^2 multiplied for log(n) $\endgroup$ – Samuele Bianchi Nov 24 '19 at 11:00
  • $\begingroup$ I have changed my answer accordingly. $\endgroup$ – Farhad Rahmanifard Nov 24 '19 at 12:46
  • 1
    $\begingroup$ This is wrong. $3n$ is always greater than $2n$ and yet $O(3n) = O(2n)$. $\endgroup$ – Raphael Nov 25 '19 at 21:23
  • $\begingroup$ Thanks for your comment @Raphael, but your example shows constant differences and is correct, while differences are limited to constants. Here, the difference changes the internal functions completely and mathematically comparable. $\endgroup$ – Farhad Rahmanifard Nov 26 '19 at 6:10
  • $\begingroup$ "Here, the difference changes the internal functions completely and mathematically comparable" -- mathematics don't care about whether you change $n$ to $2n$ or $n^2$, per se -- they are different functions. "Greater" has a clear mathematical definition. What you are doing is to explain asymptotics using asymptotics -- that's not useful at all. Instead, the OP needs an explanation why $n \leadsto 2n$ is an "insignificant" change (according to Landau notation) whereas $2 \leadsto n^2$ is not. $\endgroup$ – Raphael Nov 26 '19 at 10:15

Your Answer

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