Show that the summation ∑ i to n (logi) is O(nlogn)
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!
user3196567
Updated on March 26, 2020Comments
-
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 almost 10 yearsI am really confused about Ω(n log n) , can you explain it in more details , thank you very much
-
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 almost 10 yearsDownvoter: can you explain what I can do to improve this answer?
-
human.js about 8 yearsthis 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 about 8 years@user1198898 Can you elaborate? I'm not sure how this relates to sums of powers of two.
-
aerin over 6 yearsthis is a great answer.