# Is O((n^2)*log(n)) greater than O(n^(2.5))?

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})$$?

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

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.

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

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.

• Yeah thank you, but sorry, i forgot parentheses on n^2*log(n), it's n^2 multiplied for log(n) – Samuele Bianchi Nov 24 '19 at 11:00
• I have changed my answer accordingly. – Farhad Rahmanifard Nov 24 '19 at 12:46
• This is wrong. $3n$ is always greater than $2n$ and yet $O(3n) = O(2n)$. – Raphael Nov 25 '19 at 21:23
• 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. – Farhad Rahmanifard Nov 26 '19 at 6:10
• "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. – Raphael Nov 26 '19 at 10:15