HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
asymptoticgrowthlog

Problem

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.

Solution

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

Context

StackExchange Computer Science Q#98468, answer score: 2

Revisions (0)

No revisions yet.