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

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.

• Since $f \in O(f)$ for all $f$, it's not clear what you mean by "[the] Big-Oh of ...". – Raphael Oct 11 '18 at 19:23
• It is a multiple choice question that asks for the most appropriate big-oh, the answer is O(nlogn) and I'm not sure why that is the case. – AverageStudent Oct 11 '18 at 19:27
• If you have candidate answers, try computing the limit of the respective fractions and use the lemma from the reference question I linked. – Raphael Oct 11 '18 at 19:29
• There is no such thing as "The big-O of a function". It's like saying "What is the integer smaller than $\pi$?" There are infinitely many. – David Richerby Oct 11 '18 at 19:38
• Would asking: Show that the expression log(n^n + n) is O(nlogn) be more appropriate? – AverageStudent Oct 11 '18 at 19:40

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.)
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$$