Why is n log n dominated by n log^2 n?
little-oh proof

An equivalent but more straightforward question would be why $\lg n$ is dominated by $\lg^2 n$, that is why $\lg n \in o(\lg^2 n)$.

Then based on the definition of little-oh we need to show that for any choice of constant $ c &gt; 0 $, we can find a constant $ n_0 $ such that the inequality $ \lg n &lt; c \lg^2n $ holds for all $ n &gt; n_0 $.

We prove that if we pick $ n_0 = \sqrt[c]{b} $ where $ b $ is the base of $ \lg $, then the definition above holds.

If $ n_0 = \sqrt[c]{b} $ then we have $ n &gt; \sqrt[c]{b} $ or $ n &gt; b^{\frac{1}{c}} $.  Now since $\lg n$ with a base $ b &gt; 1 $ is an increasing function, then $ \lg n &gt; \lg b^\frac{1}{c} $ or $ \lg n &gt; \frac{1}{c} $.  If we multiply both sides by $ c &gt; 0 $, we have $ c \lg n &gt; 1 $.  Now we can multiply both sides by $ \lg n &gt; 0$ (Note that for $ \lg n &gt; 0 $ to be true, we must have $ n_0 \geqslant 1 $ which leads to $ \sqrt[c]{b} \geqslant 1 $ or $ b^\frac{1}{c} \geqslant 1$ which results in $ \lg b^{\frac{1}{c}} \geqslant \lg 1 $ or $ \frac{1}{c} \geqslant 0 $ or $ c &gt; 0 $; which is already guaranteed.) to have
$$
 c \lg^2 n &gt; \lg n .
$$
This is what we needed to show.



Big-Oh proof sketch

A slightly different but related question could be why $\lg n$ is bounded above by $\lg^2 n$, that is why $\lg n \in O(\lg^2 n)$.

The answer is that since $\lg n &gt; 1$ for $n$ larger than the base of $\lg$, then if we raise $\lg n$ to any power greater than $1$ (including power of $2$), it will be larger than $\lg n$ itself.

(We could rather argue that since we proved that $ \lg n \in o( \lg^2 n) $, it follows from $ o(f) \subset O(f) $ that $ \lg n \in O( \lg^2 n) $.)



Note

So yes, the rule of $n^a &gt; n^b$ if $a &gt; b $ and $ n &gt; 1 $ does apply here.  Note that this rule is equivalent to the statement that any exponential function with a base greater than $1$ is an increasing function.