How to show $n^k log(n^k) = o(n^{log(n)}) $

Question

Not sure how to show that $n^k log(n^k) = o(n^{log(n)}) $ where $o$ is little-Oh and $k$ is a constant. I mean I really do not know how even to start. Any hints?

Answer 1

Since $k$ is assumed to be a constant, then you are basically comparing a polynomial growth ($n^{O(1)}$) to a superpolynomial one ($n^{\omega(1)}$).

An idea of the proof:

• $n^k\log(n^k) = k n^k\log n = o(n^{k+1})$

• $(k+1)\log n = o(\log^2 n)$

• $n^{k+1} = 2^{(k+1)\log n}$, while $n^{\log n} = 2^{\log^2 n}$