3
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Since $f \in O(f)$ for all $f$, it's not clear what you mean by "[the] Big-Oh of ...". $\endgroup$ – Raphael♦ Oct 11 '18 at 19:23
  • $\begingroup$ 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. $\endgroup$ – AverageStudent Oct 11 '18 at 19:27
  • $\begingroup$ If you have candidate answers, try computing the limit of the respective fractions and use the lemma from the reference question I linked. $\endgroup$ – Raphael♦ Oct 11 '18 at 19:29
  • $\begingroup$ 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. $\endgroup$ – David Richerby Oct 11 '18 at 19:38
  • $\begingroup$ Would asking: Show that the expression log(n^n + n) is O(nlogn) be more appropriate? $\endgroup$ – AverageStudent Oct 11 '18 at 19:40
2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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$

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.