patternMinor
Asymptotic growth of $\log(n^n + n)$
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.
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.)
\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.