Menu
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?
344
This is known as a closed-form solution, and the process of replacing the summation with its closed-form solution is known as solving the summation. For example, the summation ∑ni=11 is simply the expression “1” summed n times (remember that i ranges from 1 to n).
Save this answer. Show activity on this post. So, O(N*log(N)) is far better than O(N^2) . It is much closer to O(N) than to O(N^2) .
The time complexity for inserting the elements in the array is O ( N ) O(N) O(N) and for traversing the array to calculate the sum is O ( N ) O(N) O(N). Thus overall time complexity is O ( N ) O(N) O(N).
So for higher values n, n*log(n) becomes greater than n. And that is why O(nlogn) > O(n). "Usually the base is always less than 4." The base is neither usually nor always less than 4.
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!
127
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
