n*log n and n/log n against polynomial running time
$\log n$ is the inverse of $2^n$.  Just as $2^n$ grows faster than any polynomial $n^k$ regardless of how large a finite $k$ is, $\log n$ will grow slower than any polynomial functions $n^k$ regardless of how small a nonzero, positive $k$ is.

$n / \log n$ vs $n^k$, for $k &lt; 1$ is identical to:
$n / \log n$ vs $n / n^{1-k}$

as $n^{1-k} &gt; \log n$ for large $n$, $n / \log n &gt; n^k$ for $k &lt; 1$ and large $n$.