Time complexity and Stirlings approximation

Question

We have an operation that is $O(\sum_{i=1}^{n^2}\log(i))$. Is this valid?:

$= O(\log (n^2!)) = \{\text{Stirling}\} = O(\log((n^2)^{n^2})) = O(n^2 \log(n^2)) = O(n^2 \log(n))$

If so, what's an 'easier' argument?

Answer 1

Yes, it's valid since $\log a_n \ll \log b_n$ if $a_n \ll b_n$ and $a_n \to \infty$. And it's definitely true that $(n^2)! \ll (n^2)^{n^2}$. It isn't necessary to use Stirling's formula to see this though, since

$$ 1 \times 2 \times \cdots \times n^2 < n^2 \times n^2 \times \cdots \times n^2 = (n^2)^{n^2}. $$

If you're trying to show that the estimate is best-possible then you can use the fact that

$$ \sum_{i=1}^{n^2} \log i \sim \int_1^{n^2} \log x\,dx. $$