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?

What is $k$ here, a constant? – Clement C. Oct 07 '15 at 23:03 — Clement C., Oct 07 '15 at 23:03
For large enough $n$, you have $\log (n^k) \leqslant n$. – Daniel Fischer Oct 07 '15 at 23:05 — Daniel Fischer, Oct 07 '15 at 23:05

score 3 · Accepted Answer · answered Oct 07 '15 at 23:07

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

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

1 Answers1