How to show working for summing of Big O notation

Question

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

Answer 1

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.

Answer 2

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?