Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Trying to simplify the following expressions in $n$ to find its order of growth. I want to show the simplification separately from the order of growth

$$\sum_{k=1}^{n} k \log k = \Theta(n^2 \log n)$$

Any help with solving this one ? :( lost. Can someone break it down it stages please

share|improve this question
    
    
is there a good document to teach me this stuff ? –  ferron Mar 19 '12 at 8:32
    
That comment was intended for the future :-) Right now your problem is more basic :-) –  Aryabhata Mar 19 '12 at 8:33
    
It is in Aryabhata's link but note $\int x \; \log_e (x) \; dx = \frac12 x^2 \log_e(x) - \frac{x^2}{4} + c$ –  Henry Mar 19 '12 at 8:51

4 Answers 4

Note that $k\log k$ is an increasing function, i.e. as $k$ increases, so does $k \log k$. Also note that the terms are non-negative (we are talking $\log$ to base $2$).

So you can get an upper bound as follows:

$$ \sum_{k=1}^{n} k \log k \le \sum_{k=1}^{n} n \log n = n^2 \log n$$

You can also get a lower bound by considering only the last $\frac{n}{2}$ terms. I will leave that to you as an exercise.

Next step would be to combine the two bounds to show that the sum is indeed $\theta(n^2\log n)$.

share|improve this answer
    
Of course this is true even if the base of the logarithms is not 2. –  Gerry Myerson Mar 19 '12 at 8:57
    
@GerryMyerson: Yes, as long as we pick the base to get $\gt 1$. –  Aryabhata Mar 19 '12 at 15:42
Can someone break it down it stages please
  1. Find the important part.
  2. Approximate the important part.
  3. Show the important part behaves the way you want.
  4. Show the unimportant part has a negligible contribution.
  5. Double-check you've gotten all of the inequalities right.
  6. Combine the information to prove the theorem.

To see Aryabhata's method in this light:

  • To find an upper bound, he just took the whole sequence as the important part, and made a very crude approximation. This was good enough to get to step 6.
  • To find a lower bound, he recognized two things:

    • The very crude approximation to the whole sequence doesn't work, because the terms can be too small
    • The final terms in the sequence are large

    so, he took the last half as the important part, made the crude approximation, and again that was good enough to jump straight to part 6.

share|improve this answer

Using the Euler-Maclaurin Sum Formula yields the asymptotic expansion $$ \sum_{k=1}^{n}k\log(k)=\frac12n^2\log(n)-\frac14n^2+\frac12n\log(n)+\frac{1}{12}\log(n)+O(1) $$

share|improve this answer

Note that

$\qquad \displaystyle \sum\limits_{i=1}^n iH_i = \frac{n(n+1)}{2}H_n - \frac{n(n-1)}{4}$

taken for instance from the TCS cheat sheet. With $H_n \sim \ln n$, this does what you want.

share|improve this answer

Your Answer

 
discard

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.