How to show working for summing of Big O notation

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)$$

• – D.W.
Commented Apr 28, 2021 at 8:49
• 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))$.
– plop
Commented Apr 28, 2021 at 14:17
• Analysis of @plop's mistake in my answer Addition 1. Commented Jul 21, 2021 at 14:01

So expanding on what zkutch said in their answer, we can take out the $$O(lgn)$$ from the summation as follows: $$$$\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}$$$$ And hence arrive at the answer you intuitively assumed is correct.

– plop
Commented Apr 28, 2021 at 17:08
• Check the answer you linked for Addition 1. Everything is ok. Commented Jul 21, 2021 at 12:31

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

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".

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?

• 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$.
– plop
Commented Apr 28, 2021 at 14:18
• 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. Commented Apr 28, 2021 at 16:33
• 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$.
– plop
Commented Apr 28, 2021 at 17:05
• 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. Commented Apr 28, 2021 at 19:53