2
$\begingroup$

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

  • 0
    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$2012-03-19

4 Answers 4

5

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

  • 0
    @GerryMyerson: Yes, as long as we pick the base to get $\gt 1$.2012-03-19
4

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

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

1

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.