patternModerate
Is O((n^2)*log(n)) greater than O(n^(2.5))?
Viewed 0 times
greaterthanlog
Problem
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})$?
Solution
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.
$\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.
Context
StackExchange Computer Science Q#117558, answer score: 16
Revisions (0)
No revisions yet.