How do i prove that $\log_3 (((n + (n \mod i))^k) !) = O((n^k)\log(n))$.

Question

based on simple examples we know that $\log(n!)$ belongs to $O(n\log n)$ and that $f(n)$ belongs to $O(g(n))$ only if $f(n) \leq c*g(n)$ for all $n>k$ where $c>0$ and $k>0$,

but how does this work with the $\log_3(((n+(n \mod i))^k)!) = O((n^k)\log(n))$.

Answer 1

In the worst case, we can assume $n>i$. $$\log_3((n + n\mod i)^k)!) = (\log 3)^{-1} \log((n + n\mod i)^k)!) = O(((2n)^k)!)= O((2n)^k\log(2n)^k)= O(k n^k\log (2n))= O(n^k\log(n)).$$