How does $n^c \lg n, 0<c<1$ compare to other common time complexities
$O(n^c \log n)$ is above $O(n^c)$ but below $O(n^{c+\varepsilon})$ for any $\varepsilon &gt; 0$. This is true for any $c \geq 0$, including $c &lt; 1$.

For example, $n^{0.5} \log n$ is not in $O(n^{0.5})$ but is in $O(n^{0.500001})$.

This is one of the reasons for the invention of the "soft O" notation $\tilde{O}(n^c)$, defined as the union of $O(n^c (\log n)^d)$ for all $d \geq 0$. Soft O allows you to fudge log factors and focus on the most important part, which is the highest-order polynomial exponent.