Comparison of $(\log^* n)!$ and $(n\log n)^b$
For sufficiently large values of $n$, and $b&gt;0$:
$$
( \log^*n )! &lt; ( \log \log n )! &lt; (\log \log n)^{\log \log n} = 2^{(\log\log n) \log \log \log n} \in o(2^{b \log n}) \subset o( (n \log n)^b ).
$$