The equation below is intuitively correct, but how do you show that this is actually the case? What is the working out needed?

$$\sum_{i=1}^{n-1}O(\lg n)=O(n\lg n)$$


So expanding on what zkutch said in their answer, we can take out the $O(lgn)$ from the summation as follows: \begin{equation} \begin{split} \sum_{1}^{n-1} 1 \cdot O(lgn) &= O(lgn) \cdot \sum_{1}^{n-1} 1\\ &= O(lgn) \cdot (1 + 1 + ... +_{n-1~times})\\ &= O(lgn) \cdot (n - 1)\\ &= O(nlgn) \end{split} \end{equation} And hence arrive at the answer you intuitively assumed is correct.

  • 1
    $\begingroup$ Check the links under the question. That answer that you linked to is wrong. $\endgroup$ – plop Apr 28 at 17:08
  • $\begingroup$ Check the answer you linked for Addition 1. Everything is ok. $\endgroup$ – zkutch Jul 21 at 12:31

Summand inside sum is not depend on summation index, then pull it out and you have n−1 before log.

Addition 1.

I specially copy above @plop's comment in case to keep it:

The equation is not correct in general. For example, $i\ln(n)\in O(\ln(n))$, but $\sum_{i=1}^{n-1}i\ln(n)=\frac{n(n-1)}{2}\ln(n)\notin O(n\ln(n))$.

Now about error in this reasoning: it's mistake to write $i\ln(n)\in O(\ln(n))$, when $i$ is in range from $1$ to $n$. In such case $i$ is not constant, but dependent on $n$. Obviously for each $i$ we have such $j$ for which $i=n-j$, but, hope, is clear that sentence $(n-j)\ln(n)\in O(\ln(n))$ is false. There is also some other subtle and very important detail, which I'll write in next addition - I beg pardon for mentioned in comment below "nearest days", but I have it almost ready and "hope in nearest days I'll find time to write it down".

Addition for silent down voters.

Down voting without argumentation doesn't help neither OP, neither readers, nor writers and nor this site - I sincerely welcome anyone who openly criticizes any proposal I wrote. An open, professional discussion of issues and responsibility for own words is the best friend and helper in our work. Dear down voter, I thought for a long time before writing Addition 1., I even found similar considerations in well-known sources (let's not name them for now) - do you have something to say/write?

  • 2
    $\begingroup$ The summands are sets and the sum of those sets include all choices of elements inside those sets. As a consequence, some of the elements in the sum are obtained by making a different choice for each summand, making it depend on $i$. $\endgroup$ – plop Apr 28 at 14:18
  • $\begingroup$ Result of sum of sets does not depend on "choice" made from each summand: really there is no choice. Sum of sets contain element means for this element exists its part from one summand and its part from another summand. Existence is exact understanding of choice. Here is another very dangerous point which is not listed in all links brought by D.W. and which also needs to be cleared in plop's example. I hope in nearest days I'll find time to write it down. $\endgroup$ – zkutch Apr 28 at 16:33
  • 1
    $\begingroup$ I never said "Result of sum of sets does not depend on "choice" made from each summand". Your answer is wrong because the sum of the sets contains all choices of sums of elements from the sets. In particular, it contains sums in which the choices of elements does depend on the $i$. $\endgroup$ – plop Apr 28 at 17:05
  • $\begingroup$ Am I claiming that you said something? I pointed out that the formal basis for choice is the existential quantifier. I also wrote that I will try to reveal this topic in the coming days and I think it would be very easy to wait for my answer before the down vote, especially since your interpretation needs deep clarification. $\endgroup$ – zkutch Apr 28 at 19:53
  • $\begingroup$ It wasn't me who downvoted either answer. I only added the comments. $\endgroup$ – plop Apr 28 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.