Skip to main content
3 of 6
Replace git with LaTeX code
Anatolii
  • 261
  • 1
  • 6

In order to compare 2 complexities just calculate a limit of their ratios as below (here we use L'Hôpital's rule to simplify calculating a limit for $\frac{\ln(k)}{k}$:

$\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}}=\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}=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}=\frac{2} {\infty}=0$

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

Anatolii
  • 261
  • 1
  • 6