Show that the summation ∑ i to n (logi) is O(nlogn)

29,379

If you just need to show that the sum is O(n log n), you can show that

Σ log i ≤ Σ log n = n log n

Therefore, your function is O(n log n). If you want to be even more formal, you can use the constants c = 1 and n0 = 1.

The more interesting question is to show that the sum is Θ(n log n) by proving an Ω(n log n) lower bound. To do this, note that the sum is greater than or equal to the sum of the last n / 2 terms in the summation. Each of those terms in the summation is at least log (n / 2). This gives a lower bound of (n / 2) log(n / 2) = (n / 2) (log n - log 2), which is Ω(n log n). Therefore, your summation is O(n log n) and Ω(n log n), so it's Θ(n log n).

Hope this helps!

Share:
29,379
user3196567
Author by

user3196567

Updated on March 26, 2020

Comments

  • user3196567
    user3196567 over 3 years

    One way I thought it works is that we can say that ∑_i^{n (log i)} < ∑_i^{n (log n)} and then try to argue that it's O(n log n), but where to go from here? Any suggestions?

  • user3196567
    user3196567 almost 10 years
    I am really confused about Ω(n log n) , can you explain it in more details , thank you very much
  • templatetypedef
    templatetypedef almost 10 years
    @user3196567 Sure! Think of it this way: your summation is log 1 + log 2 + ... + log n. Split this into log 1 + log 2 + ... + log (n/2) + log (n/2 + 1) + ... + log n. This sum is certainly at least as large as log(n / 2) + log(n/2 + 1) + log(n/2 + 2) + ... + log n. That sum, in turn, is at least as large as log(n / 2) + log(n / 2) + ... + log(n / 2) = (n / 2) log(n / 2). You can then use the formal definition of Ω to prove that (n / 2) log(n / 2) = Ω(n log n), from which the result follows.
  • templatetypedef
    templatetypedef almost 10 years
    Downvoter: can you explain what I can do to improve this answer?
  • human.js
    human.js about 8 years
    this method is easier but does not always give the right answer. Example would be 1 +2 + 4 + ... + 2^n <= .2^n . which does not provide the right answer for this
  • templatetypedef
    templatetypedef about 8 years
    @user1198898 Can you elaborate? I'm not sure how this relates to sums of powers of two.
  • aerin
    aerin over 6 years
    this is a great answer.