Asymptotic growth of $\log(n^n + n)$
You could continue with
\begin{align*}
    \log n + \log (n^{n-1}+1)
        &amp;\leq \log n + \log(2n^{n-1})\\
        &amp;= \log n + (n-1)\log 2n\\
        &amp;= \log n + (n-1)\log 2 + (n-1)\log n\\
        &amp;= O(n\log n)\,.
\end{align*}
(Leaving out whatever steps you feel are obvious.)