Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to transform this: $$n \log n + n \log(n^{\log n})$$ into big O notation.

I can't get to reduce the right part of the addition...

Neither of these work: $$n^{\log n} \log(n)\qquad\text{nor}\qquad n \log(\log n * n)$$

I was planning to get them to multiply together, and then I would have only 1 small function.

How do I reduce the right part ?

share|cite|improve this question
I can't quite see your formatting – Rustyn Feb 10 '13 at 18:23
thanks, I fixed the formating a bit. – Dave Feb 10 '13 at 18:24
up vote 6 down vote accepted

Notice that $n\log(n^{\log n}) = n (\log n)^2$. So $$ n\log n + n \log(n^{\log n}) = n\log n + n \log^2 n $$ $$ = n \log n(1+\log n) = n (\log n) O(\log n) = O(n \log^2 n) $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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