Asymptotic growth of $\log(n^n + n)$

Question

I would like to know if my understanding of this is correct:

The question asks to show that the Big-Oh of the following function is $O(n\log(n))$

$$ \log(n^n + n) $$

I think the first step is to play with the expression so:

$$ \log(n^n + n) = \log(n(n^{n-1}+1)) = \log(n) + \log(n^{n-1}+1) $$ However, I don't know what to do next. Please help me move forward. Thanks.

Answer 1

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

Answer 2

Hint: use $\log(a+b) = \log a + \log(1+b/a)$ this;

Write the $\log(n^n+n)$ as $\log(n^n+n) = \log(n^n) + \log(1+n/n^n)$

$ \log(n^n) + \log(1+n/n^n) \in \mathcal{O}(n \log n)$

note $n/n^n \rightarrow 0$ as $n \rightarrow \infty$