10

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?

nbro
  • 15,395
  • 32
  • 113
  • 196
user3196567
  • 323
  • 1
  • 4
  • 7
  • This is clearly related to the efficiency of `std::map` in C++ ! – Damien Nov 30 '18 at 09:15
  • Time complexity analysis of software is relevant for programming, voting to reopen. – joanis Jan 08 '21 at 20:08
  • It should say so in the question to make it more obvious though. However, if so, I would agree to reopen. –  Jan 09 '21 at 11:17

1 Answers1

23

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!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • 3
    I am really confused about Ω(n log n) , can you explain it in more details , thank you very much – user3196567 Jan 16 '14 at 05:17
  • 8
    @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 Jan 16 '14 at 21:05
  • 7
    Downvoter: can you explain what I can do to improve this answer? – templatetypedef Jan 16 '14 at 21:09
  • 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 – human.js Oct 24 '15 at 08:31
  • @user1198898 Can you elaborate? I'm not sure how this relates to sums of powers of two. – templatetypedef Oct 24 '15 at 18:16
  • 1
    this is a great answer. – aerin Aug 15 '17 at 19:54