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(nlgn)$$
Summand inside sum is not depend on summation index, then pull it out and you have n−1 before log.